public class Euler457 {

    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 tonelliShanks(long n, long p) {
        if (p == 2)
            return n & 1;
        if (n == 0)
            return 0;
        if (modPow(n, (p - 1) / 2, p) != 1)
            return 0;
        if ((p & 3) == 3)
            return modPow(n, (p + 1) / 4, p);

        long q = p - 1;
        int s = 0;
        while ((q & 1) == 0) {
            q >>= 1;
            s++;
        }

        long z = 2;
        while (modPow(z, (p - 1) / 2, p) != p - 1) {
            z++;
        }

        long m = s;
        long c = modPow(z, q, p);
        long t = modPow(n, q, p);
        long r = modPow(n, (q + 1) / 2, p);

        while (t != 1) {
            long tt = t;
            long i = 0;
            while (tt != 1 && i < m) {
                tt = (tt * tt) % p;
                i++;
            }

            long shift = m - i - 1;
            long b = modPow(c, 1L << shift, p);
            r = (r * b) % p;
            long b2 = (b * b) % p;
            t = (t * b2) % p;
            c = b2;
            m = i;
        }

        return r;
    }

    static long liftRoot(long p, long r) {
        long deriv = (2 * r + p - 3) % p;
        long invDeriv = modPow(deriv, p - 2, p);

        long fr = r * r - 3 * r - 1;
        long q = fr / p;

        long negQ = -(q % p);
        negQ %= p;
        if (negQ < 0) {
            negQ += p;
        }

        long t = (negQ * invDeriv) % p;
        return r + t * p;
    }

    public static String solve() {
        int limit = 10000000;
        boolean[] isPrime = new boolean[limit + 1];
        for (int i = 2; i <= limit; i++)
            isPrime[i] = true;

        for (int i = 2; (long) i * i <= limit; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= limit; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        boolean[] residue = new boolean[13];
        residue[1] = true;
        residue[3] = true;
        residue[4] = true;
        residue[9] = true;
        residue[10] = true;
        residue[12] = true;

        long sum = 0;
        for (int p = 2; p <= limit; p++) {
            if (!isPrime[p] || p == 2 || p == 13)
                continue;
            if (!residue[p % 13])
                continue;

            long s = tonelliShanks(13 % p, p);
            long inv2 = (p + 1) / 2;

            long r1 = ((3 + s) * inv2) % p;
            long r2 = ((3 + p - s) * inv2) % p;

            long n1 = liftRoot(p, r1);
            long n2 = liftRoot(p, r2);

            sum += (n1 < n2) ? n1 : n2;
        }

        return Long.toString(sum);
    }

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