import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

public class Euler407 {
    static int[] buildSpf(int n) {
        int[] spf = new int[n + 1];
        List<Integer> primes = new ArrayList<>(n / 10);

        for (int i = 2; i <= n; i++) {
            if (spf[i] == 0) {
                spf[i] = i;
                primes.add(i);
            }
            for (int p : primes) {
                long x = (long) i * p;
                if (x > n)
                    break;
                spf[(int) x] = p;
                if (p == spf[i])
                    break;
            }
        }
        return spf;
    }

    static int invMod(int a, int mod) {
        int b = mod;
        int u = 1;
        int v = 0;
        while (b != 0) {
            int t = a / b;
            int tempA = a - t * b;
            a = b;
            b = tempA;
            int tempU = u - t * v;
            u = v;
            v = tempU;
        }
        if (u < 0)
            u += mod;
        return u;
    }

    static String solve() {
        int limit = 10000000;
        int[] spf = buildSpf(limit);

        long total = IntStream.rangeClosed(1, limit)
                .parallel()
                .mapToLong(n -> {
                    if (n == 1)
                        return 0;

                    int[] primePowers = new int[10];
                    int x = n;
                    int k = 0;

                    while (x > 1) {
                        int p = spf[x];
                        int pe = 1;
                        while (x % p == 0) {
                            x /= p;
                            pe *= p;
                        }
                        primePowers[k++] = pe;
                    }

                    if (k == 1)
                        return 1;

                    int full = 1 << k;
                    int[] subsetProd = new int[full];
                    subsetProd[0] = 1;

                    for (int mask = 1; mask < full; mask++) {
                        int lsb = mask & -mask;
                        int bit = Integer.numberOfTrailingZeros(lsb);
                        subsetProd[mask] = subsetProd[mask ^ lsb] * primePowers[bit];
                    }

                    int best = 1;
                    for (int mask = 1; mask < full - 1; mask++) {
                        int u = subsetProd[mask];
                        int v = n / u;
                        int inv = invMod(u % v, v);
                        int a = (int) (((long) u * inv) % n);
                        if (a > best)
                            best = a;
                    }

                    return best;
                })
                .sum();

        return Long.toString(total);
    }

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