#include <stdio.h>

/* The digital root (also repeated digital sum) of a non-negative 
 * integer is the (single digit) value obtained by an iterative process
 * of summing digits, on each iteration using the result from the previous
 * iteration to compute a digit sum. The process continues until a 
 * single-digit number is reached.
 */

/* bit 0-2: top, mid, bottom
 * bit 3-6: top-left, top-right, bottom-left, bottom-right
 */

enum {
	TOP = 1,
	MID = 2,
	BOTTOM = 4,
	TL = 8,
	TR = 16,
	BL = 32,
	BR = 64
};

unsigned char lines[10] = {
	TOP | BOTTOM | TL | TR | BL | BR,
	TR | BR,
	TOP | MID | BOTTOM | TR | BL,
	TOP | MID | BOTTOM | TR | BR,
	MID | TL | TR | BR,
	TOP | MID | BOTTOM | TL | BR,
	TOP | MID | BOTTOM | TL | BL | BR,
	TOP | TL | TR | BR,
	TOP | MID | BOTTOM | TL | TR | BL | BR,
	TOP | MID | BOTTOM | TL | TR | BR
};

int popcount(unsigned char x)
{
	int count = 0;
	while (x) {
		count += (x&1);
		x >>= 1;
	}
	return count;
}

void get_digits(int x, int a[])
{
	int i = 0;
	do {
		a[i] = x % 10;
		x /= 10;
		i++;
	} while (x);
	a[i] = -1;
}

int clock_sam(int x)
{
	int digits[10];
	int l = 0;
	while (x >= 10) {
		get_digits(x, digits);
		x = 0;
		for (int i = 0; digits[i] != -1; i++) {
			l += popcount(lines[digits[i]]) * 2;
			x += digits[i];
		}
	}
	l += popcount(lines[x]) * 2;
	return l;
}

int clock_max(int x)
{
	int digits[10],next_digits[10], nx;
	int l = 0;
	get_digits(x, digits);
	nx = 0;
	for (int i = 0; digits[i] != -1; i++) {
		l += popcount(lines[digits[i]]);
		nx += digits[i];
	}
	while (x >= 10) {
		get_digits(nx, next_digits);
		int i;
		/* calculate the diff */
		for (i = 0; next_digits[i] != -1; i++) {
			l += popcount(lines[digits[i]]^lines[next_digits[i]]);
		}
		while (digits[i] != -1) {
			l += popcount(lines[digits[i]]);
			i++;
		}
		/* get the next */
		x = nx;
		nx = 0;
		for (i = 0; next_digits[i] != -1; i++) {
			digits[i] = next_digits[i];
			nx += next_digits[i];
		}
		digits[i] = -1;
	}
	l += popcount(lines[x]);
	return l;
}

int isoddprime(int x)
{
	for (int i = 3; i*i <= x; i += 2) {
		if (x % i == 0)
			return 0;
	}
	return 1;
}

int main()
{
	int sum = 0;
	const int A = 10*1000*1000;
	const int B = 20*1000*1000;
	for (int i = A+1; i < B; i += 2) {
		if (isoddprime(i)) {
			sum += clock_sam(i) - clock_max(i);
		}
	}
	printf("%d\n", sum);
}