BBD - Mr Toothless and His Number Theory

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 <= 1010).

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


Added by:Alim
Date:2014-05-12
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2024-09-07 17:55:52
In all tests B - A <= 10^5. It's important condition.
2014-05-13 18:44:07 nazmuS sakiB
A~B ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.