import java.util.ArrayList;

public class Euler659 {
    static final long kMod18 = 1000000000000000000L;

    static long modPow(long base, long exp, long mod) {
        long result = 1 % mod;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                // To avoid overflow in long * long % mod, use BigInteger or Russian Peasant
                // Here mod is at most p <= 2*10^7, so base*base easily fits in long.
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        return result;
    }

    static long tonelliShanks(long n, long p) {
        if (n == 0)
            return 0;
        if (p == 2)
            return n;
        if (modPow(n, (p - 1) / 2, p) != 1)
            return 0;
        if (p % 4 == 3)
            return modPow(n, (p + 1) / 4, p);

        long q = p - 1;
        int s = 0;
        while ((q & 1) == 0) {
            q >>= 1;
            ++s;
        }

        long z = 2;
        while (modPow(z, (p - 1) / 2, p) != p - 1)
            ++z;

        long m = s;
        long c = modPow(z, q, p);
        long t = modPow(n, q, p);
        long r = modPow(n, (q + 1) / 2, p);

        while (t != 1) {
            long tt = t;
            long i = 0;
            while (tt != 1) {
                tt = (tt * tt) % p;
                ++i;
            }
            long b = modPow(c, 1L << (m - i - 1), p);
            r = (r * b) % p;
            c = (b * b) % p;
            t = (t * c) % p;
            m = i;
        }

        return r;
    }

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

    static long solveCase(int kmax) {
        int limit = 2 * kmax;
        ArrayList<Integer> primes = sievePrimes(limit);

        long[] rem = new long[kmax + 1];
        int[] lastSmall = new int[kmax + 1];

        for (int k = 1; k <= kmax; ++k) {
            rem[k] = 4L * k * k + 1L;
            lastSmall[k] = 1;
        }

        for (int p : primes) {
            if (p == 2 || (p & 3) != 1)
                continue;

            long root = tonelliShanks(p - 1, p);
            if (root == 0)
                continue;

            long inv2 = (p + 1) / 2L;
            int k1 = (int) ((root * inv2) % p);
            int k2 = (k1 == 0) ? 0 : (p - k1);

            int start1 = k1;
            if (start1 <= 0)
                start1 += p;
            for (int k = start1; k <= kmax; k += p) {
                long v = rem[k];
                if (v % p != 0)
                    continue;
                do {
                    v /= p;
                } while (v % p == 0);
                rem[k] = v;
                lastSmall[k] = p;
            }

            if (k2 != k1) {
                int start2 = k2;
                if (start2 <= 0)
                    start2 += p;
                for (int k = start2; k <= kmax; k += p) {
                    long v = rem[k];
                    if (v % p != 0)
                        continue;
                    do {
                        v /= p;
                    } while (v % p == 0);
                    rem[k] = v;
                    lastSmall[k] = p;
                }
            }
        }

        long ans = 0;
        for (int k = 1; k <= kmax; ++k) {
            long tail = rem[k];
            long lpf = lastSmall[k];
            if (tail > lpf)
                lpf = tail;

            ans += lpf % kMod18;
            if (ans >= kMod18)
                ans %= kMod18;
        }

        return ans;
    }

    public static String solve() {
        long ans = solveCase(10000000);
        return Long.toString(ans);
    }

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