public class Euler315 {
    static int[] digitMasks() {
        int T = 1 << 0;
        int M = 1 << 1;
        int B = 1 << 2;
        int TL = 1 << 3;
        int TR = 1 << 4;
        int BL = 1 << 5;
        int BR = 1 << 6;

        return new int[] {
                T | B | TL | TR | BL | BR,
                TR | BR,
                T | M | B | TR | BL,
                T | M | B | TR | BR,
                M | TL | TR | BR,
                T | M | B | TL | BR,
                T | M | B | TL | BL | BR,
                T | TL | TR | BR,
                T | M | B | TL | TR | BL | BR,
                T | M | B | TL | TR | BR
        };
    }

    static int digitSum(int n) {
        int s = 0;
        while (n > 0) {
            s += n % 10;
            n /= 10;
        }
        return s;
    }

    static int segmentCountNumber(int n, int[] masks) {
        int total = 0;
        while (n > 0) {
            total += Integer.bitCount(masks[n % 10]);
            n /= 10;
        }
        return total;
    }

    static int transitionCost(int from, int to, int[] masks) {
        int cost = 0;
        while (from > 0 || to > 0) {
            int a = (from > 0) ? masks[from % 10] : 0;
            int b = (to > 0) ? masks[to % 10] : 0;
            cost += Integer.bitCount(a ^ b);
            from /= 10;
            to /= 10;
        }
        return cost;
    }

    public static String solve() {
        int from = 10000000;
        int to = 20000000;
        int[] masks = digitMasks();

        byte[] isPrime = new byte[to];
        for (int i = 2; i < to; i++)
            isPrime[i] = 1;
        for (int p = 2; (long) p * p < to; ++p) {
            if (isPrime[p] == 1) {
                for (int q = p * p; q < to; q += p) {
                    isPrime[q] = 0;
                }
            }
        }

        long totalDiff = 0;
        int[] chain = new int[16];

        for (int p = from; p < to; ++p) {
            if (isPrime[p] == 0)
                continue;

            int cSize = 0;
            int curr = p;
            while (true) {
                chain[cSize++] = curr;
                if (curr < 10)
                    break;
                curr = digitSum(curr);
            }

            int samCost = 0;
            for (int i = 0; i < cSize; i++) {
                samCost += 2 * segmentCountNumber(chain[i], masks);
            }

            int mxCost = transitionCost(0, chain[0], masks);
            for (int i = 1; i < cSize; i++) {
                mxCost += transitionCost(chain[i - 1], chain[i], masks);
            }
            mxCost += transitionCost(chain[cSize - 1], 0, masks);

            totalDiff += (samCost - mxCost);
        }

        return String.valueOf(totalDiff);
    }

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