import java.math.BigInteger;

public class Euler876 {

    static BigInteger euclidSum(BigInteger a, BigInteger b) {
        if (a.compareTo(b) < 0) {
            BigInteger temp = a;
            a = b;
            b = temp;
        }
        BigInteger sum = BigInteger.ZERO;
        while (b.compareTo(BigInteger.ZERO) > 0) {
            BigInteger[] divAndRem = a.divideAndRemainder(b);
            sum = sum.add(divAndRem[0]);
            a = b;
            b = divAndRem[1];
        }
        return sum;
    }

    static BigInteger computeFPower(int k, BigInteger[] pow2, BigInteger[] pow3, BigInteger[] pow5) {
        BigInteger a = pow2[k].multiply(pow3[k]);
        BigInteger b = pow2[k].multiply(pow5[k]);
        BigInteger twoA = a.shiftLeft(1);
        BigInteger twoB = b.shiftLeft(1);
        BigInteger twoAb = a.add(b).shiftLeft(1);

        BigInteger N = pow2[2 * k + 2].multiply(pow3[k]).multiply(pow5[k]);
        BigInteger total = BigInteger.ZERO;

        for (int e2 = 0; e2 <= 2 * k + 2; ++e2) {
            BigInteger v2 = pow2[e2];
            for (int e3 = 0; e3 <= k; ++e3) {
                BigInteger v23 = v2.multiply(pow3[e3]);
                for (int e5 = 0; e5 <= k; ++e5) {
                    BigInteger q = v23.multiply(pow5[e5]);
                    BigInteger p = N.divide(q);

                    if (q.compareTo(p) > 0)
                        continue;
                    if (p.add(q).testBit(0))
                        continue;

                    BigInteger s1 = euclidSum(twoA.max(q), twoA.min(q));
                    BigInteger s2 = euclidSum(twoB.max(q), twoB.min(q));
                    BigInteger f = s1.min(s2);

                    total = total.add(f);
                    if (p.add(q).compareTo(twoAb) < 0) {
                        total = total.add(f.subtract(BigInteger.ONE));
                    }
                }
            }
        }
        return total;
    }

    public static String solve() {
        int maxK = 18;
        int maxPow2 = 2 * maxK + 2;

        BigInteger[] pow2 = new BigInteger[maxPow2 + 1];
        pow2[0] = BigInteger.ONE;
        for (int i = 1; i <= maxPow2; ++i) {
            pow2[i] = pow2[i - 1].shiftLeft(1);
        }

        BigInteger[] pow3 = new BigInteger[maxK + 1];
        BigInteger[] pow5 = new BigInteger[maxK + 1];
        pow3[0] = BigInteger.ONE;
        pow5[0] = BigInteger.ONE;

        BigInteger three = BigInteger.valueOf(3);
        BigInteger five = BigInteger.valueOf(5);

        for (int i = 1; i <= maxK; ++i) {
            pow3[i] = pow3[i - 1].multiply(three);
            pow5[i] = pow5[i - 1].multiply(five);
        }

        BigInteger total = BigInteger.ZERO;
        for (int k = 1; k <= maxK; ++k) {
            total = total.add(computeFPower(k, pow2, pow3, pow5));
        }

        return total.toString();
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}