chandu-and-primes-1

Chandu is a big fan of primes. He defines another kind of primes alpha-primes. Alpha-primes are defined as primes for which there exists some suffix of a given number which is a prime. For example, 12 is not prime but 12 is alpha prime as there exists a suffix which is a prime. In case of 12, 2 is prime therefore 12 is alpha-prime.
Now, he gives you Q queries of the form L R for which you have to calculate how many alpha-primes are there in the range [L, R].

Input : 
First line contains a single integer Q denoting no. of queries.
Next Q line contains two space separated integers L and R.

Output : 
For each query output the count of alpha-primes in the range [L, R]

Constraints : 
1 ≤ Q ≤ 10^6
1 ≤ L ≤ R ≤ 10^6

SAMPLE INPUT
4
1 2
10 14
110 114
5 5

SAMPLE OUTPUT
1
3
3
1

Explanation

Query 1 2
1 is neither prime nor alpha-prime.
2 is prime and there exists a suffix which is 2 itself which is prime therefore 2 is alpha-prime.
Therefore total count in range 1 2 is 1.
Query 10 14
10 is not aplha-prime as its suffix 0 and 10 are not prime.
11 is alpha-prime as its suffix 11 is prime.
12 is alpha-prime as its suffix 2 is prime. 
13 is alpha-prime as its suffix 3 is prime. 
14 is not alpha-prime as its suffix 4 and 14 are not prime.
Therefore total count in range 10 14 is 3.

Source: hackerearth | Difficulty: EASY
Tags: Number theory

Ad-hoc


Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import math
MAX = 1000001
ap = [1] * MAX
ap[0] = ap[1] = 0
for i in range(4, MAX, 2):
	ap[i] = 0
for i in range(3, MAX, 2):
	if ap[i] == 1:
		for j in range(2*i, MAX, i):
			ap[j] = 0
low_num = 1
high_num = 10
add = 10
while(low_num != 1000000):
	for i in range(low_num, high_num):
		if ap[i] == 1:
			for j in range(add, MAX - add + 1, add):
				ap[j + i] = 1
	low_num *= 10
	high_num *= 10
	add *= 10
for i in range(1, MAX):
	ap[i] += ap[i-1]
for i in range(int(input())):
	l, r = list(map(int, input().split()))
	print(ap[r] - ap[l-1])