Shaad likes number theory very much. So his teacher Mr. Toothless Give him a task. He has given two numbers A and B he has to calculate number of palindromic primes between A and B inclusive.

Input

Input starts with an integer T (= 15), denoting the number of test cases.

Each case contains a blank line two integers A, B (0 <= A < B <= 10¹⁰).

Output

For each case, print the expected result.

Example

Input:
2
1 5
7 11

Output:
3
2

Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology