Problem Statement:

The ThunderBolt team at Orange labs is ranked to be one of the best teams in software development. So to qualify the skills of any candidates joining The ThunderBullets team there is a problem to be solved before joining.

Given a range of numbers from start to end, the candidate has to calculate how many numbers exist within this range following two rules:

1- The number is prime (1 isn't prime).

2- The sum of all digits inside that number is also prime.

For example: 11 is a prime number and 1 + 1 = 2 which is also prime.

Can you join The ThunderBolt team?

Input Format:

The first line contains an integer T, the number of test cases. Followed by T lines, each line contains a test case which consists of 2 integers start and end, 1 <= start <= end <= 10000.

Output Format:

For each test case, print a single line containing the number of numbers that follows the two rules within the range.

Sample Input:

2
2 5
1 12

Sample Output:

3
5