import java.util.ArrayList;
import java.util.List;

public class Euler611 {
    static long isqrt(long x) {
        long r = (long) Math.sqrt(x);
        while ((r + 1) * (r + 1) <= x)
            r++;
        while (r * r > x)
            r--;
        return r;
    }

    static int ilog2(long x) {
        if (x <= 0)
            return 0;
        return 63 - Long.numberOfLeadingZeros(x);
    }

    static List<Integer> sievePrimesInt(int n) {
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 2; i <= n; i++)
            isPrime[i] = true;
        for (int p = 2; (long) p * p <= n; p++) {
            if (isPrime[p]) {
                for (int j = p * p; j <= n; j += p) {
                    isPrime[j] = false;
                }
            }
        }
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (isPrime[i])
                primes.add(i);
        }
        return primes;
    }

    static long chiInt(long x) {
        if ((x & 1) == 0)
            return 0;
        return (x & 3) == 1 ? 1 : -1;
    }

    static long sumChi1To(long m) {
        long c1 = (m + 3) / 4;
        long c3 = (m + 1) / 4;
        return c1 - c3;
    }

    static class PrimeCountMod4 {
        long n;
        long sq;
        List<Long> vals;
        long[] gPi;
        long[] gChi;
        int[] id1;
        int[] id2;
        List<Integer> primes;
        long[] prefChiPrime;

        PrimeCountMod4(long n) {
            this.n = n;
            this.sq = isqrt(n);
            this.primes = sievePrimesInt((int) sq);

            this.vals = new ArrayList<>();
            for (long l = 1; l <= n;) {
                long w = n / l;
                vals.add(w);
                l = n / w + 1;
            }

            int m = vals.size();
            gPi = new long[m];
            gChi = new long[m];
            id1 = new int[(int) sq + 1];
            id2 = new int[(int) sq + 1];

            for (int i = 0; i < m; i++) {
                long w = vals.get(i);
                gPi[i] = (w >= 2) ? (w - 1) : 0;
                gChi[i] = (w >= 1) ? (sumChi1To(w) - 1) : 0;
                if (w <= sq)
                    id1[(int) w] = i;
                else
                    id2[(int) (n / w)] = i;
            }

            prefChiPrime = new long[primes.size() + 1];
            for (int i = 0; i < primes.size(); i++) {
                prefChiPrime[i + 1] = prefChiPrime[i] + chiInt(primes.get(i));
            }

            for (int i = 0; i < primes.size(); i++) {
                long p = primes.get(i);
                long p2 = p * p;
                if (p2 > n)
                    break;
                long chiP = chiInt(p);

                for (int j = 0; j < m; j++) {
                    long w = vals.get(j);
                    if (w < p2)
                        break;
                    long q = w / p;
                    int idx = (q <= sq) ? id1[(int) q] : id2[(int) (n / q)];
                    gPi[j] -= gPi[idx] - i;
                    if (chiP != 0) {
                        gChi[j] -= chiP * (gChi[idx] - prefChiPrime[i]);
                    }
                }
            }
        }

        int id(long x) {
            return (x <= sq) ? id1[(int) x] : id2[(int) (n / x)];
        }

        long pi(long x) {
            return gPi[id(x)];
        }

        long sumChiPrimes(long x) {
            return gChi[id(x)];
        }

        long pi1(long x) {
            if (x < 5)
                return 0;
            long pix = pi(x);
            long oddPrimes = pix - 1;
            long s = sumChiPrimes(x);
            return (oddPrimes + s) / 2;
        }
    }

    static int[] sieveSpf(int n) {
        int[] spf = new int[n + 1];
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (spf[i] == 0) {
                spf[i] = i;
                primes.add(i);
            }
            for (int p : primes) {
                long v = (long) p * i;
                if (v > n)
                    break;
                spf[(int) v] = p;
                if (p == spf[i])
                    break;
            }
        }
        return spf;
    }

    static long countB(long N, byte[] parityOdd1Mod4) {
        long lim = isqrt(N);
        long ans = 0;
        for (long m = 1; m <= lim; m += 2) {
            if (parityOdd1Mod4[(int) m] == 0)
                continue;
            long base = m * m;
            long t = N / base;
            ans += ilog2(t) + 1;
        }
        return ans;
    }

    static long countAEvenV2(long N, PrimeCountMod4 pc, List<Integer> primesSmall) {
        long S1 = 0;
        long tmax = isqrt(N);
        for (long t = 1; t <= tmax; t++) {
            long R = N / (t * t);
            if (R < 5)
                break;
            long L = N / ((t + 1) * (t + 1));
            long cnt = pc.pi1(R) - pc.pi1(L);
            S1 += t * cnt;
        }

        long corr = 0;
        long cbrtN = 10000;
        for (int p : primesSmall) {
            if (p > cbrtN)
                break;
            if (p % 4 != 1)
                continue;
            long T = isqrt(N / p);
            corr += T / p;
        }

        long total = S1 - corr;

        for (int p : primesSmall) {
            if (p % 4 != 1)
                continue;
            long powVal = (long) p * p * p * p * p;
            if (powVal > N || powVal < 0)
                break;
            long p4 = (long) p * p * p * p;
            while (powVal <= N && powVal > 0) {
                long T = isqrt(N / powVal);
                total += T - T / p;
                if (powVal > N / p4)
                    break;
                powVal *= p4;
            }
        }
        return total;
    }

    static long F(long N, PrimeCountMod4 pc, List<Integer> primesSmall, int[] spf, byte[] parity) {
        long aEven = countAEvenV2(N, pc, primesSmall);
        long aOdd = countAEvenV2(N / 2, pc, primesSmall);
        return aEven + aOdd + countB(N, parity);
    }

    public static String solve() {
        long Nmax = 1000000000000L;
        PrimeCountMod4 pc = new PrimeCountMod4(Nmax);

        int LIM = 1000000;
        int[] spf = sieveSpf(LIM);
        List<Integer> primesSmall = sievePrimesInt(LIM);

        byte[] parity = new byte[LIM + 1];
        for (int x = 2; x <= LIM; x++) {
            int n = x;
            byte par = 0;
            while (n > 1) {
                int p = spf[n];
                int e = 0;
                while (n % p == 0) {
                    n /= p;
                    e ^= 1;
                }
                if (e != 0 && (p % 4 == 1)) {
                    par ^= 1;
                }
            }
            parity[x] = par;
        }

        long ans = F(Nmax, pc, primesSmall, spf, parity);
        return Long.toString(ans);
    }

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