public class Euler437 {
    static int[] spfArr;

    public static String solve() {
        int limit = 100000000;
        int half = limit / 2 + 1;
        spfArr = new int[half];
        int root = (int) Math.sqrt(limit);
        for (int i = 3; i <= root; i += 2)
            if (spfArr[i >> 1] == 0)
                for (int j = i * i; j <= limit; j += 2 * i)
                    if (spfArr[j >> 1] == 0)
                        spfArr[j >> 1] = i;
        int[] primes;
        {
            java.util.List<Integer> pl = new java.util.ArrayList<>();
            pl.add(2);
            for (int p = 3; p <= limit; p += 2)
                if (spfArr[p >> 1] == 0)
                    pl.add(p);
            primes = pl.stream().mapToInt(Integer::intValue).toArray();
        }
        long total = 0;
        for (int p : primes) {
            if (p <= 3)
                continue;
            if (p == 5) {
                total += 5;
                continue;
            }
            if (p % 5 != 1 && p % 5 != 4)
                continue;
            long s5 = tonelliSqrt5(p);
            if (s5 < 0)
                continue;
            long inv2 = (p + 1L) / 2;
            long r1 = (1 + s5) % p * inv2 % p, r2 = (1 + p - s5) % p * inv2 % p;
            int[] factors = factorUnique(p - 1);
            if (isPrimRoot(r1, p, factors) || isPrimRoot(r2, p, factors))
                total += p;
        }
        return String.valueOf(total);
    }

    static long modPow(long b, long e, long m) {
        long r = 1;
        b %= m;
        while (e > 0) {
            if ((e & 1) != 0)
                r = r * b % m;
            b = b * b % m;
            e >>= 1;
        }
        return r;
    }

    static long tonelliSqrt5(int p) {
        if (p == 2)
            return 1;
        if (modPow(5, (p - 1) / 2, p) != 1)
            return -1;
        if (p % 4 == 3)
            return modPow(5, (p + 1L) / 4, p);
        long q = p - 1;
        int s = 0;
        while (q % 2 == 0) {
            q /= 2;
            s++;
        }
        int z = 2;
        while (modPow(z, (p - 1) / 2, p) != p - 1)
            z++;
        long c = modPow(z, q, p), x = modPow(5, (q + 1) / 2, p), t = modPow(5, q, p);
        int m = s;
        while (t != 1) {
            long tt = t;
            int i = 0;
            while (tt != 1 && i < m) {
                tt = tt * tt % p;
                i++;
            }
            long b = modPow(c, 1L << (m - i - 1), p);
            x = x * b % p;
            t = t * b % p * b % p;
            c = b * b % p;
            m = i;
        }
        return x;
    }

    static int[] factorUnique(int n) {
        java.util.List<Integer> f = new java.util.ArrayList<>();
        if (n % 2 == 0) {
            f.add(2);
            while (n % 2 == 0)
                n /= 2;
        }
        while (n > 1) {
            int ff = (n & 1) != 0 ? (spfArr[n >> 1] == 0 ? n : spfArr[n >> 1]) : 2;
            f.add(ff);
            while (n % ff == 0)
                n /= ff;
        }
        return f.stream().mapToInt(Integer::intValue).toArray();
    }

    static boolean isPrimRoot(long g, int p, int[] factors) {
        long phi = p - 1;
        for (int q : factors)
            if (modPow(g, phi / q, p) == 1)
                return false;
        return true;
    }

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