MAIN111 - Strictly not a Prime


Tim defines an integer as "Strictly not a Prime", if no subsequence(considering the integer as a string of digits) of the integer is a prime. He needs your help in finding how many such integers are present between two given integers A and B(including A and B).

Input

First line contains an integer T(1 <= T <= 100000) which denotes the total number test cases. Each test case consists of two integers A and B (1 <= A, B <= 100000) on a single line.

Output

For each test case, print the total count of integers which are "Strictly not a prime" between A and B(including A and B) as per tim.

Example

Input:
2
3 6
7 10
Output:
2
3

hide comments
sanket17: 2020-01-24 12:19:00

I m getting compilation error showing (to_string and stoi() ) methods are not declared in this scope.
the code is running on my local complier

Last edit: 2020-01-24 12:19:19
nayem_ahmed: 2019-12-10 16:08:42

After using Sieve why i get TLE? Please help me

divyansh_soni: 2018-08-06 23:10:45

silly mistake can give WA:
a>b then swap :)

viratian_070: 2017-06-26 20:57:17

nice question...silly mistake costed me 4 wa...bitmask and seive will work

bsiddhartha: 2017-06-22 07:39:44

no subsequence(considering the integer as a string of digits)
169{1,6,9}...19 isprime .....many wa for not reading this statement
4609 is strictly prime r not??

Last edit: 2017-06-22 08:59:23
Dushyant Singh: 2017-03-31 21:23:13

A>B possible.

Answer for

1

1 100000

is

2568

holmesherlock: 2017-03-31 20:46:55

excellent prob, use of bitmask,sieve etc.will give u A.C.

sultania23: 2017-03-24 11:11:28

easy one..

shahzada: 2017-03-01 06:15:07

Precompute and answer all queries in O(1).

abhishekx300: 2016-05-12 14:36:48

i/p:
1
1 100000
o/p:
2567


Added by:amit karmakar
Date:2011-08-15
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem used in - http://www.spoj.pl/MAIN11/