import java.util.ArrayList;
import java.math.BigInteger;

public class Euler864 {

    static final long kTarget = 123567101113L;
    static final long kBGlobal = 60000000L;
    static final int kMaxRoots = 128;

    static class PrimeRoot {
        int p;
        long p2;
        long r1;
        long r2;

        PrimeRoot(int p, long p2, long r1, long r2) {
            this.p = p;
            this.p2 = p2;
            this.r1 = r1;
            this.r2 = r2;
        }
    }

    static class Roots {
        int size = 0;
        long[] vals = new long[kMaxRoots];
    }

    static ArrayList<PrimeRoot> gPrimes = new ArrayList<>();
    static ArrayList<Integer> gSmallPrimes = new ArrayList<>();

    static long modPow(long base, long exp, long mod) {
        long res = 1 % mod;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1)
                res = BigInteger.valueOf(res).multiply(BigInteger.valueOf(base)).mod(BigInteger.valueOf(mod))
                        .longValue();
            base = BigInteger.valueOf(base).multiply(BigInteger.valueOf(base)).mod(BigInteger.valueOf(mod)).longValue();
            exp >>= 1;
        }
        return res;
    }

    static long[] egcd(long a, long b) {
        if (b == 0)
            return new long[] { a, 1, 0 };
        long[] res = egcd(b, a % b);
        long g = res[0];
        long x1 = res[1];
        long y1 = res[2];
        long x = y1;
        long y = x1 - BigInteger.valueOf(y1).multiply(BigInteger.valueOf(a / b)).longValue();
        return new long[] { g, x, y };
    }

    static long modInv(long a, long mod) {
        long[] res = egcd(a, mod);
        if (res[0] != 1)
            return 0;
        long x = res[1] % mod;
        if (x < 0)
            x += mod;
        return x;
    }

    static long sqrtMinusOneModP(long p) {
        for (long b = 2; b < p; ++b) {
            if (modPow(b, (p - 1) / 2, p) == p - 1) {
                return modPow(b, (p - 1) / 4, p);
            }
        }
        return -1;
    }

    static PrimeRoot buildPrimeRoot(int p) {
        long r0 = sqrtMinusOneModP(p);
        long p2 = (long) p * p;
        long m = (r0 * r0 + 1) / p;
        long inv = modPow((2 * r0) % p, p - 2, p);
        long k = (p - (m % p)) % p;
        k = BigInteger.valueOf(k).multiply(BigInteger.valueOf(inv)).mod(BigInteger.valueOf(p)).longValue();
        long r = r0 + (long) p * k;
        return new PrimeRoot(p, p2, r, p2 - r);
    }

    static void initPrimeRoots(long limit) {
        boolean[] isPrime = new boolean[(int) limit + 1];
        java.util.Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (long i = 2; i * i <= limit; ++i) {
            if (isPrime[(int) i]) {
                for (long j = i * i; j <= limit; j += i) {
                    isPrime[(int) j] = false;
                }
            }
        }
        for (int p = 5; p <= limit; ++p) {
            if (isPrime[p] && (p % 4 == 1)) {
                gPrimes.add(buildPrimeRoot(p));
            }
        }
    }

    static void initSmallPrimes(int limit) {
        boolean[] isPrime = new boolean[limit + 1];
        java.util.Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= limit; ++i) {
            if (isPrime[i]) {
                for (int j = i * i; j <= limit; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        for (int i = 2; i <= limit; ++i) {
            if (isPrime[i])
                gSmallPrimes.add(i);
        }
    }

    static long countSolutions(long n, long mod, Roots roots) {
        long q = n / mod;
        long s = n - q * mod;
        long count = q * roots.size;
        for (int i = 0; i < roots.size; ++i) {
            if (roots.vals[i] <= s)
                count++;
        }
        return count;
    }

    static void combineRoots(Roots roots, PrimeRoot pr, long modOld, Roots out) {
        long modNew = pr.p2;
        long inv = modInv(modOld % modNew, modNew);
        out.size = roots.size * 2;
        int idx = 0;
        for (int i = 0; i < roots.size; ++i) {
            long ro = roots.vals[i];
            long roMod = ro % modNew;
            long[] rList = { pr.r1, pr.r2 };
            for (int j = 0; j < 2; ++j) {
                long diff = rList[j] - roMod;
                if (diff < 0)
                    diff += modNew;
                long t = BigInteger.valueOf(diff).multiply(BigInteger.valueOf(inv)).mod(BigInteger.valueOf(modNew))
                        .longValue();
                long newR = ro + BigInteger.valueOf(modOld).multiply(BigInteger.valueOf(t)).longValue();
                out.vals[idx++] = newR;
            }
        }
    }

    static void dfsPart1(int startIdx, long d, long d2, Roots roots, int sign, long n, long B, long[] sum) {
        for (int i = startIdx; i < gPrimes.size(); ++i) {
            PrimeRoot pr = gPrimes.get(i);
            if (pr.p > B)
                break;
            if (d > B / pr.p)
                break;
            long nextD = d * pr.p;
            long nextD2 = nextD * nextD;
            Roots nextRoots = new Roots();
            combineRoots(roots, pr, d2, nextRoots);
            long term = countSolutions(n, nextD2, nextRoots);
            int nextSign = -sign;
            sum[0] += (long) nextSign * term;
            dfsPart1(i + 1, nextD, nextD2, nextRoots, nextSign, n, B, sum);
        }
    }

    static long countPart1(long n, long B) {
        if (B < 5)
            return 0;
        int threads = Runtime.getRuntime().availableProcessors();
        if (threads <= 0)
            threads = 4;

        long[] sums = new long[threads];
        Thread[] workers = new Thread[threads];

        for (int t = 0; t < threads; ++t) {
            final int tId = t;
            final int thr = threads;
            workers[t] = new Thread(() -> {
                long local = 0;
                for (int idx = tId; idx < gPrimes.size(); idx += thr) {
                    PrimeRoot pr = gPrimes.get(idx);
                    if (pr.p > B)
                        break;
                    long d = pr.p;
                    long d2 = d * d;
                    Roots roots = new Roots();
                    roots.size = 2;
                    roots.vals[0] = pr.r1;
                    roots.vals[1] = pr.r2;
                    long term = countSolutions(n, d2, roots);
                    local -= term;
                    long[] localArr = { local };
                    dfsPart1(idx + 1, d, d2, roots, -1, n, B, localArr);
                    local = localArr[0];
                }
                sums[tId] = local;
            });
            workers[t].start();
        }

        for (Thread th : workers) {
            try {
                th.join();
            } catch (InterruptedException e) {
            }
        }

        long total = 0;
        for (long v : sums)
            total += v;
        return total;
    }

    static boolean solveNegativePell(long k, long n, long[] xy) {
        long a0 = (long) Math.sqrt(k);
        while ((a0 + 1) * (a0 + 1) <= k)
            a0++;
        while (a0 * a0 > k)
            a0--;
        if (a0 * a0 == k)
            return false;

        long m = 0, d = 1, a = a0;
        BigInteger pPrev1 = BigInteger.ONE;
        BigInteger qPrev1 = BigInteger.ZERO;
        BigInteger pCurr = BigInteger.valueOf(a0);
        BigInteger qCurr = BigInteger.ONE;
        BigInteger nBig = BigInteger.valueOf(n);

        if (pCurr.compareTo(nBig) > 0 || qCurr.compareTo(nBig) > 0)
            return false;

        for (int step = 1;; ++step) {
            m = d * a - m;
            d = (k - m * m) / d;
            a = (a0 + m) / d;

            BigInteger aBig = BigInteger.valueOf(a);
            BigInteger pNext = aBig.multiply(pCurr).add(pPrev1);
            BigInteger qNext = aBig.multiply(qCurr).add(qPrev1);

            pPrev1 = pCurr;
            qPrev1 = qCurr;
            pCurr = pNext;
            qCurr = qNext;

            if (d == 1 && a == 2 * a0) {
                if (step % 2 == 1 && pPrev1.compareTo(nBig) <= 0 && qPrev1.compareTo(nBig) <= 0) {
                    xy[0] = pPrev1.longValue();
                    xy[1] = qPrev1.longValue();
                    return true;
                }
                return false;
            }
            if (pCurr.compareTo(nBig) > 0 || qCurr.compareTo(nBig) > 0)
                return false;
        }
    }

    static int mobiusSquarefree(long y) {
        int mu = 1;
        long tmp = y;
        for (int p : gSmallPrimes) {
            long pp = (long) p * p;
            if (pp > tmp)
                break;
            if (tmp % p == 0) {
                tmp /= p;
                if (tmp % p == 0)
                    return 0;
                mu = -mu;
            }
        }
        if (tmp > 1)
            mu = -mu;
        return mu;
    }

    static byte[] buildValidK(long kMax) {
        byte[] valid = new byte[(int) kMax + 1];
        java.util.Arrays.fill(valid, (byte) 1);
        if (kMax >= 0)
            valid[0] = 0;
        boolean[] isPrime = new boolean[(int) kMax + 1];
        java.util.Arrays.fill(isPrime, true);
        if (kMax >= 0)
            isPrime[0] = false;
        if (kMax >= 1)
            isPrime[1] = false;
        for (long i = 2; i * i <= kMax; ++i) {
            if (isPrime[(int) i]) {
                for (long j = i * i; j <= kMax; j += i)
                    isPrime[(int) j] = false;
            }
        }
        for (long p = 2; p <= kMax; ++p) {
            if (!isPrime[(int) p])
                continue;
            if (p % 4 == 3) {
                for (long j = p; j <= kMax; j += p)
                    valid[(int) j] = 0;
            }
        }
        return valid;
    }

    static long countPart2(long n, long B) {
        BigInteger bn = BigInteger.valueOf(n);
        BigInteger bB = BigInteger.valueOf(B);
        BigInteger n2 = bn.multiply(bn).add(BigInteger.ONE);
        BigInteger B2 = bB.multiply(bB);
        long kMax = n2.divide(B2).longValue();

        if (kMax <= 0)
            return 0;
        byte[] valid = buildValidK(kMax);

        int threads = Runtime.getRuntime().availableProcessors();
        if (threads <= 0)
            threads = 4;

        long[] sums = new long[threads];
        Thread[] workers = new Thread[threads];

        for (int t = 0; t < threads; ++t) {
            final int tId = t;
            final int thr = threads;
            workers[t] = new Thread(() -> {
                long local = 0;
                for (long k = 1 + tId; k <= kMax; k += thr) {
                    if (valid[(int) k] == 0)
                        continue;
                    long s = (long) Math.sqrt(k);
                    if (s * s == k)
                        continue;

                    long[] xy = new long[2];
                    if (!solveNegativePell(k, n, xy))
                        continue;
                    long x0 = xy[0];
                    long y0 = xy[1];

                    BigInteger XMul = BigInteger.valueOf(x0).multiply(BigInteger.valueOf(x0))
                            .add(BigInteger.valueOf(k).multiply(BigInteger.valueOf(y0))
                                    .multiply(BigInteger.valueOf(y0)));
                    BigInteger YMul = BigInteger.valueOf(2).multiply(BigInteger.valueOf(x0))
                            .multiply(BigInteger.valueOf(y0));
                    BigInteger YMulK = YMul.multiply(BigInteger.valueOf(k));
                    BigInteger nBig = BigInteger.valueOf(n);

                    long x = x0;
                    long y = y0;
                    while (x <= n) {
                        if (y > B) {
                            int mu = mobiusSquarefree(y);
                            if (mu != 0)
                                local += mu;
                        }
                        if (XMul.compareTo(nBig) > 0 || YMulK.compareTo(nBig) > 0)
                            break;

                        BigInteger xNext = BigInteger.valueOf(x).multiply(XMul)
                                .add(BigInteger.valueOf(y).multiply(YMulK));
                        BigInteger yNext = BigInteger.valueOf(x).multiply(YMul)
                                .add(BigInteger.valueOf(y).multiply(XMul));

                        if (xNext.compareTo(nBig) > 0)
                            break;
                        x = xNext.longValue();
                        y = yNext.longValue();
                    }
                }
                sums[tId] = local;
            });
            workers[t].start();
        }

        for (Thread th : workers) {
            try {
                th.join();
            } catch (InterruptedException e) {
            }
        }

        long total = 0;
        for (long v : sums)
            total += v;
        return total;
    }

    static long computeC(long n) {
        long B = Math.min(kBGlobal, n);
        long total = n;
        total += countPart1(n, B);
        total += countPart2(n, B);
        return total;
    }

    public static String solve() {
        initPrimeRoots(Math.min(kBGlobal, kTarget));
        initSmallPrimes(400000);
        return Long.toString(computeC(kTarget));
    }

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