BBD - Mr Toothless and His Number Theory

no tags 

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


hide comments
backer01: 2024-09-07 17:55:52

In all tests B - A <= 10^5. It's important condition.

nazmuS sakiB: 2014-05-13 18:44:07

A~B ?


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