public class Euler302 {
    static final int kPrimeSieveN = 6 * 105000;
    static int primeCount = 0;
    static int[] primes = new int[kPrimeSieveN / 4];
    static byte[] erat = new byte[kPrimeSieveN + 1];

    static int[][] divisors = new int[kPrimeSieveN + 1][24];
    static byte[] divisorsCount = new byte[kPrimeSieveN + 1];

    static long answer = 0;

    static int gcdSmall(int a, int b) {
        while (b != 0) {
            int c = a % b;
            a = b;
            b = c;
        }
        return a;
    }

    static int cubeRootFloor(long n) {
        if (n <= 1L) {
            return (int) n;
        }
        int r = (int) Math.pow(n, 1.0 / 3.0);
        while ((long) (r + 1) * (r + 1) * (r + 1) <= n)
            ++r;
        while ((long) r * r * r > n)
            --r;
        return r;
    }

    static void countRecursive(int maxPrimeIdx, int[] activeFactors, int activeCount, int gcdExpN, int gcdExpPhi,
            long lim) {
        if (lim == 0L)
            return;

        if (gcdExpN == 1) {
            int g = gcdExpPhi;
            int i = 0;
            while (i < activeCount) {
                int j = i + 1;
                while (j < activeCount && activeFactors[j] == activeFactors[i])
                    ++j;
                int cnt = j - i;
                if (cnt < 2) {
                    g = 0;
                    break;
                }
                g = gcdSmall(g, cnt);
                i = j;
            }
            if (g == 1) {
                ++answer;
            }
        }

        int minIdx = 0;
        if (activeCount >= 2) {
            if (activeFactors[activeCount - 1] != activeFactors[activeCount - 2]) {
                minIdx = activeFactors[activeCount - 1];
            } else {
                for (int k = activeCount - 2; k >= 1; --k) {
                    if (activeFactors[k] != activeFactors[k + 1] && activeFactors[k] != activeFactors[k - 1]) {
                        minIdx = activeFactors[k];
                        break;
                    }
                }
            }
        } else if (activeCount == 1) {
            minIdx = activeFactors[0];
        }

        int maxIdx = cubeRootFloor(lim);
        if (maxPrimeIdx > 0 && primes[maxPrimeIdx - 1] > maxIdx) {
            int a = 0;
            int b = maxPrimeIdx - 1;
            while (a < b - 1) {
                int c = (a + b) / 2;
                if (primes[c] > maxIdx) {
                    b = c;
                } else {
                    a = c;
                }
            }
            maxIdx = a;
        }
        if (maxIdx > maxPrimeIdx - 1) {
            maxIdx = maxPrimeIdx - 1;
        }

        int[] merged = new int[70];
        for (int j = activeCount - 1; j >= 0;) {
            int overdeg = 0;
            for (int y = j; y >= 0 && activeFactors[y] == activeFactors[j]; --y)
                ++overdeg;

            if (activeFactors[j] < maxPrimeIdx) {
                int k1 = 0, k2 = 0, mergedCount = 0;
                int idx = activeFactors[j];
                int pMinusOne = primes[idx] - 1;
                int divCnt = divisorsCount[pMinusOne];

                while (k1 < activeCount && k2 < divCnt) {
                    if (activeFactors[k1] < divisors[pMinusOne][k2]) {
                        merged[mergedCount++] = activeFactors[k1++];
                    } else {
                        merged[mergedCount++] = divisors[pMinusOne][k2++];
                    }
                }
                while (k2 < divCnt)
                    merged[mergedCount++] = divisors[pMinusOne][k2++];
                while (k1 < activeCount)
                    merged[mergedCount++] = activeFactors[k1++];

                int g2 = gcdExpPhi;
                while (mergedCount > 0 && merged[mergedCount - 1] > activeFactors[j]) {
                    int y = mergedCount - 1;
                    while (y >= 0 && merged[y] == merged[mergedCount - 1])
                        --y;
                    g2 = gcdSmall(g2, mergedCount - y - 1);
                    mergedCount = y + 1;
                }
                if (mergedCount > 0 && merged[mergedCount - 1] == activeFactors[j]) {
                    mergedCount -= overdeg;
                }

                long p = primes[idx];
                long pow = p;
                int deg = 2;
                while (pow <= lim / p) {
                    int newG1 = gcdSmall(gcdExpN, deg);
                    int newG2 = gcdSmall(g2, deg - 1 + overdeg);
                    countRecursive(idx, merged, mergedCount, newG1, newG2, lim / pow / p);

                    if (pow > (Long.MAX_VALUE / p))
                        break;
                    pow *= p;
                    ++deg;
                }
            }

            j -= overdeg;
            if (overdeg == 1)
                break;
        }

        int now = 0;
        while (now < activeCount && activeFactors[now] < minIdx)
            ++now;

        for (int idx = minIdx; idx <= maxIdx; ++idx) {
            if (now < activeCount && idx == activeFactors[now]) {
                while (now < activeCount && activeFactors[now] == idx)
                    ++now;
                continue;
            }

            int k1 = 0, k2 = 0, mergedCount = 0;
            int pMinusOne = primes[idx] - 1;
            int divCnt = divisorsCount[pMinusOne];

            while (k1 < activeCount && k2 < divCnt) {
                if (activeFactors[k1] < divisors[pMinusOne][k2]) {
                    merged[mergedCount++] = activeFactors[k1++];
                } else {
                    merged[mergedCount++] = divisors[pMinusOne][k2++];
                }
            }
            while (k2 < divCnt)
                merged[mergedCount++] = divisors[pMinusOne][k2++];
            while (k1 < activeCount)
                merged[mergedCount++] = activeFactors[k1++];

            int g2 = gcdExpPhi;
            while (mergedCount > 0 && merged[mergedCount - 1] > idx) {
                int y = mergedCount - 1;
                while (y >= 0 && merged[y] == merged[mergedCount - 1])
                    --y;
                g2 = gcdSmall(g2, mergedCount - y - 1);
                mergedCount = y + 1;
            }

            long p = primes[idx];
            long pow = p * p;
            int deg = 3;
            while (pow <= lim / p) {
                int newG1 = gcdSmall(gcdExpN, deg);
                int newG2 = gcdSmall(g2, deg - 1);
                countRecursive(idx, merged, mergedCount, newG1, newG2, lim / pow / p);

                if (pow > (Long.MAX_VALUE / p))
                    break;
                pow *= p;
                ++deg;
            }
        }
    }

    static void prepareData() {
        primes[0] = 2;
        primes[1] = 3;
        primeCount = 2;
        erat[1] = 1;

        int sq = (int) Math.sqrt(kPrimeSieveN);
        for (int i = 0; i <= sq; i += 6) {
            if (erat[i + 1] == 0) {
                int p = i + 1;
                int step = p * 6;
                for (int j = p * p; j <= kPrimeSieveN; j += step)
                    erat[j] = 1;
                for (int j = p * (p + 4); j <= kPrimeSieveN; j += step)
                    erat[j] = 1;
                primes[primeCount++] = p;
            }
            if (erat[i + 5] == 0) {
                int p = i + 5;
                int step = p * 6;
                for (int j = p * p; j <= kPrimeSieveN; j += step)
                    erat[j] = 1;
                for (int j = p * (p + 2); j <= kPrimeSieveN; j += step)
                    erat[j] = 1;
                primes[primeCount++] = p;
            }
        }

        int start = sq - (sq % 6) + 6;
        for (int i = start; i < kPrimeSieveN; i += 6) {
            if (erat[i + 1] == 0)
                primes[primeCount++] = i + 1;
            if (erat[i + 5] == 0)
                primes[primeCount++] = i + 5;
        }

        for (int i = 0; i < primeCount; ++i) {
            for (long deg = primes[i]; deg <= kPrimeSieveN;) {
                for (int j = (int) deg; j <= kPrimeSieveN; j += (int) deg) {
                    divisors[j][divisorsCount[j]++] = i;
                }
                if (deg <= kPrimeSieveN / primes[i]) {
                    deg *= primes[i];
                } else {
                    break;
                }
            }
        }
    }

    public static String solve() {
        prepareData();
        answer = 0;
        int[] rootFactors = new int[70];
        countRecursive(primeCount, rootFactors, 0, 0, 0, 1000000000000000000L);
        return String.valueOf(answer);
    }

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