public class Euler455 {

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

    static long fValue(long n, long mod) {
        long x = 0;
        long[] seen = new long[80];
        int seenCount = 0;

        for (int iter = 0; iter < 80; iter++) {
            long nx = modPow(n, x, mod);
            if (nx == x) {
                return x > 0 ? x : 0;
            }
            boolean repeated = false;
            for (int i = 0; i < seenCount; i++) {
                if (seen[i] == nx) {
                    repeated = true;
                    break;
                }
            }
            if (repeated) {
                return 0;
            }
            seen[seenCount++] = nx;
            x = nx;
        }

        long nx = modPow(n, x, mod);
        if (nx == x && x > 0) {
            return x;
        }
        return 0;
    }

    public static String solve() {
        int limit = 1000000;
        long mod = 1000000000L;
        long sum = 0;
        for (int n = 2; n <= limit; n++) {
            sum += fValue(n, mod);
        }
        return Long.toString(sum);
    }

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