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

public class Euler565 {
    static BigInteger tri(long n) {
        return BigInteger.valueOf(n).multiply(BigInteger.valueOf(n + 1)).divide(BigInteger.valueOf(2));
    }

    static long modPow(long a, long e, long mod) {
        long r = 1 % mod;
        a %= mod;
        while (e > 0) {
            if ((e & 1) != 0)
                r = (long) ((BigInteger.valueOf(r).multiply(BigInteger.valueOf(a))).remainder(BigInteger.valueOf(mod))
                        .longValue());
            a = (long) ((BigInteger.valueOf(a).multiply(BigInteger.valueOf(a))).remainder(BigInteger.valueOf(mod))
                    .longValue());
            e >>= 1;
        }
        return r;
    }

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

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

    static List<Integer> sievePrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 2; i <= n; i++)
            isPrime[i] = true;
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    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 orderModPrime(long a, long p) {
        long ord = p - 1;
        long[] factors = { 2, 3, 7 };
        for (long f : factors) {
            while (ord % f == 0 && modPow(a, ord / f, p) == 1) {
                ord /= f;
            }
        }
        return ord;
    }

    static List<Long> primesModMinusOne(long N, long p, List<Integer> primesUpToSqrtN) {
        long kMax = (N + 1) / p;
        byte[] isComp = new byte[(int) (kMax + 1)];

        for (int r : primesUpToSqrtN) {
            if (r == p)
                continue;
            long rr = (long) r * r;
            if (rr > N)
                break;

            long inv = modInv(p % r, r);
            long kMin = (rr + 1 + p - 1) / p;

            long k = inv;
            if (k < kMin) {
                long t = (kMin - k + r - 1) / r;
                k += t * r;
            }
            for (; k <= kMax; k += r) {
                isComp[(int) k] = 1;
            }
        }

        List<Long> out = new ArrayList<>(2200000);
        for (long k = 1; k <= kMax; k++) {
            if (isComp[(int) k] == 0) {
                long q = p * k - 1;
                if (q >= 2 && q <= N)
                    out.add(q);
            }
        }
        return out;
    }

    static class BadPrime {
        long q;
        List<Integer> badExps;

        BadPrime(long q, List<Integer> badExps) {
            this.q = q;
            this.badExps = badExps;
        }
    }

    static List<BadPrime> badPrimesOther(long N, long p, int sqrtN, List<Integer> primes) {
        List<BadPrime> bad = new ArrayList<>();
        for (int qInt : primes) {
            if (qInt > sqrtN)
                break;
            long q = qInt;
            if (q == p)
                continue;
            long a = q % p;
            if (a == 1 || a == p - 1)
                continue;

            long ord = orderModPrime(a, p);
            int emax = 0;
            long pw = 1;
            while (pw <= N / q) {
                pw *= q;
                emax++;
            }

            List<Integer> exps = new ArrayList<>();
            for (int m = 1;; m++) {
                long e = ord * m - 1;
                if (e > emax)
                    break;
                exps.add((int) e);
            }
            if (!exps.isEmpty()) {
                bad.add(new BadPrime(q, exps));
            }
        }
        return bad;
    }

    static BigInteger sumExactBadExp(long N, long q, int e) {
        BigInteger qpow = BigInteger.ONE;
        for (int i = 0; i < e; i++)
            qpow = qpow.multiply(BigInteger.valueOf(q));
        long M = BigInteger.valueOf(N).divide(qpow).longValue();
        long Mq = M / q;
        BigInteger sumNotDivQ = tri(M).subtract(BigInteger.valueOf(q).multiply(tri(Mq)));
        return qpow.multiply(sumNotDivQ);
    }

    static BigInteger sumPairExact(long N, long q, int eq, long r, int er) {
        BigInteger qpow = BigInteger.ONE;
        for (int i = 0; i < eq; i++)
            qpow = qpow.multiply(BigInteger.valueOf(q));
        BigInteger rpow = BigInteger.ONE;
        for (int i = 0; i < er; i++)
            rpow = rpow.multiply(BigInteger.valueOf(r));
        BigInteger P = qpow.multiply(rpow);

        if (P.compareTo(BigInteger.valueOf(N)) > 0)
            return BigInteger.ZERO;

        long M = BigInteger.valueOf(N).divide(P).longValue();
        long Mq = M / q;
        long Mr = M / r;
        long Mqr = M / (q * r);

        BigInteger sumCoprime = tri(M)
                .subtract(BigInteger.valueOf(q).multiply(tri(Mq)))
                .subtract(BigInteger.valueOf(r).multiply(tri(Mr)))
                .add(BigInteger.valueOf(q).multiply(BigInteger.valueOf(r)).multiply(tri(Mqr)));

        return P.multiply(sumCoprime);
    }

    static int upperBound(List<Long> list, int start, long val) {
        int left = start;
        int right = list.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) > val)
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }

    static BigInteger computeS(long N, long p) {
        int sqrtN = (int) Math.sqrt(N);
        List<Integer> primes = sievePrimes(sqrtN);

        List<Long> p2 = primesModMinusOne(N, p, primes);
        List<BadPrime> other = badPrimesOther(N, p, sqrtN, primes);

        BigInteger singles = BigInteger.ZERO;
        for (long q : p2) {
            singles = singles.add(sumExactBadExp(N, q, 1));
        }
        for (BadPrime bp : other) {
            for (int e : bp.badExps) {
                singles = singles.add(sumExactBadExp(N, bp.q, e));
            }
        }

        BigInteger pairs = BigInteger.ZERO;

        int itSmallEnd = upperBound(p2, 0, sqrtN);
        for (int i = 0; i < itSmallEnd; i++) {
            long q = p2.get(i);
            long lim = N / q;
            int itrEnd = upperBound(p2, i + 1, lim);
            for (int j = i + 1; j < itrEnd; j++) {
                long r = p2.get(j);
                pairs = pairs.add(sumPairExact(N, q, 1, r, 1));
            }
        }

        for (BadPrime bp : other) {
            for (int e : bp.badExps) {
                BigInteger rpow = BigInteger.ONE;
                for (int i = 0; i < e; i++)
                    rpow = rpow.multiply(BigInteger.valueOf(bp.q));
                if (rpow.compareTo(BigInteger.valueOf(N)) > 0)
                    continue;
                long lim = BigInteger.valueOf(N).divide(rpow).longValue();
                for (long q : p2) {
                    if (q > lim)
                        break;
                    pairs = pairs.add(sumPairExact(N, q, 1, bp.q, e));
                }
            }
        }

        for (int i = 0; i < other.size(); i++) {
            for (int j = i + 1; j < other.size(); j++) {
                for (int ei : other.get(i).badExps) {
                    for (int ej : other.get(j).badExps) {
                        pairs = pairs.add(sumPairExact(N, other.get(i).q, ei, other.get(j).q, ej));
                    }
                }
            }
        }

        return singles.subtract(pairs);
    }

    public static String solve() {
        return computeS(100000000000L, 2017).toString();
    }

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