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

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/

hide comments
2013-03-27 04:29:06 munai
i didnt get the problem. someone please make me understand.
2013-03-25 07:54:26 Swapnil R.Mehta
Pls swap 'a' and 'b' if (a>b)
:)
2012-11-24 20:07:41 Snehasish Roy ;)
Nice Problem :)
2012-06-29 10:27:14 npsabari
Swap A and B if A > B.
2012-04-30 06:09:52 Abhishek Mishra
guys don't use miller rabin in this ques it provide wrong answer if u r using it then use iterations upto 8 .I have just accepted using miller rabin my time is 4.11.
while using sieve my tym is 1.33..:)
2011-09-07 22:03:48 Pratham Khandelwal
Thank Abhijith for the Note
2011-08-29 14:42:27 vipin
can some one pls post a few more test cases. i am stuck with WA..pls..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.