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
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

newbie: 2015-11-14 19:26:38

finally ac after 6 wa's good luck :) 0 & 1 are strictly not prime good luck :)

newbie: 2015-11-14 19:25:17

1. Swap if(a>b)
2. output for
1
1 100000
2568


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/