1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include<stdio.h>
int sum(int m) {
	int sum=0;
	while(m!=0) {
		sum+=m%10;
		m=m/10;
	}
	return sum;
}
int a[1000010]= {0};
int b[1000010]= {0};
int main() {
	int m,k;
	for(m=2; m<=1000000; m++) {
		if(!a[m]) {
			for(k=m+m; k<=1000000; k+=m) {
				a[k]=1;
			}
		}
	}
	for(k=2; k<=1000000; k++) {
		b[k]=b[k-1];
		if(!a[k]) {
			if(!a[sum(k)]) {
				b[k]++;
			}
		}
	}
	int i,T,L,R;
	scanf("%d",&T);
	for(i=1; i<=T; i++) {
		scanf("%d %d",&L,&R);
		printf("Case #%d: %d\n",i,b[R]-b[L-1]);
	}
	return 0;
}