import java.math.BigInteger;

public class Euler717 {
    static long mulMod(long a, long b, long mod) {
        BigInteger bigA = BigInteger.valueOf(a);
        BigInteger bigB = BigInteger.valueOf(b);
        BigInteger bigMod = BigInteger.valueOf(mod);
        return bigA.multiply(bigB).remainder(bigMod).longValue();
    }

    static long powMod(long base, long exp, long mod) {
        if (mod == 1)
            return 0;
        long result = 1 % mod;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                result = mulMod(result, base, mod);
            }
            base = mulMod(base, base, mod);
            exp >>= 1;
        }
        return result;
    }

    static long gValue(long p) {
        long e = powMod(2, p, p - 1);
        long r = powMod(2, e, p);
        long t = mulMod(r, (p + 1) / 2, p);

        long mod = p * p;
        long twoPMod = powMod(2, p, mod);
        long u = mulMod(t, twoPMod, mod);

        if (u < r) {
            u += mod;
        }
        u -= r;

        return u / p;
    }

    public static String solve() {
        int n = 10000000;
        byte[] isPrime = new byte[n];
        java.util.Arrays.fill(isPrime, (byte) 1);
        if (n > 0)
            isPrime[0] = 0;
        if (n > 1)
            isPrime[1] = 0;

        for (int i = 2; (long) i * i < n; ++i) {
            if (isPrime[i] != 0) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = 0;
                }
            }
        }

        long totalSum = 0;
        for (int p = 3; p < n; p += 2) {
            if (isPrime[p] != 0) {
                totalSum += gValue(p);
            }
        }

        return Long.toString(totalSum);
    }

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