import java.util.stream.IntStream;

public class Euler451 {
    static final int LIMIT = 20000000;

    static int modInverse(int a, int mod) {
        long x0 = 1, y0 = 0;
        long x1 = 0, y1 = 1;
        long aa = a, mm = mod;

        while (mm != 0) {
            long q = aa / mm;
            long aa2 = aa - q * mm;
            aa = mm;
            mm = aa2;

            long nx = x0 - q * x1;
            x0 = x1;
            x1 = nx;
        }

        if (aa != 1)
            return 0;
        long v = x0 % mod;
        if (v < 0)
            v += mod;
        return (int) v;
    }

    static int[] buildSpf(int limit) {
        int[] spf = new int[limit + 1];
        for (int i = 0; i <= limit; i++)
            spf[i] = i;
        for (int i = 2; i * i <= limit; i++) {
            if (spf[i] == i) {
                for (int j = i * i; j <= limit; j += i) {
                    if (spf[j] == j) {
                        spf[j] = i;
                    }
                }
            }
        }
        return spf;
    }

    static int computeI(int n, int[] spf) {
        int[] sums = new int[256];
        int target = n - 1;
        sums[0] = target;
        int count = 1;
        int best = 1;

        int nn = n;
        while (nn != 1) {
            int p = spf[nn];
            long q = 1;
            do {
                nn /= p;
                q *= p;
            } while (nn % p == 0);

            if (q == 2)
                continue;

            long m = n / q;
            long inv = modInverse((int) (m % q), (int) q);
            long b = (m * inv) % n;
            long delta2 = (2L * b) % n;
            long deltaHalf = 0;
            long deltaHalfPlusTwo = 0;

            if ((q & 1) == 0 && q >= 8) {
                long half = q / 2;
                deltaHalf = (half * b) % n;
                deltaHalfPlusTwo = ((half + 2) * b) % n;
            }

            int currentCount = count;
            for (int j = 0; j < currentCount; j++) {
                int base = sums[j];

                long sLong = base + delta2;
                if (sLong >= n)
                    sLong -= n;
                int s = (int) sLong;
                sums[count++] = s;
                if (s > best && s < target)
                    best = s;

                if ((q & 1) == 0 && q >= 8) {
                    long s1Long = base + deltaHalf;
                    if (s1Long >= n)
                        s1Long -= n;
                    int s1 = (int) s1Long;
                    sums[count++] = s1;
                    if (s1 > best && s1 < target)
                        best = s1;

                    long s2Long = base + deltaHalfPlusTwo;
                    if (s2Long >= n)
                        s2Long -= n;
                    int s2 = (int) s2Long;
                    sums[count++] = s2;
                    if (s2 > best && s2 < target)
                        best = s2;
                }
            }
        }
        return best;
    }

    public static String solve() {
        int[] spf = buildSpf(LIMIT);
        int chunkSize = 16384;
        int totalChunks = (LIMIT - 3 + 1 + chunkSize - 1) / chunkSize;

        long totalSum = IntStream.range(0, totalChunks).parallel().mapToLong(chunkIdx -> {
            int start = 3 + chunkIdx * chunkSize;
            int end = Math.min(LIMIT, start + chunkSize - 1);
            long localSum = 0;
            for (int n = start; n <= end; n++) {
                localSum += computeI(n, spf);
            }
            return localSum;
        }).sum();

        return Long.toString(totalSum);
    }

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