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
2011-08-20 19:15:29 abhijith reddy d
Note: Sometimes A>B.
2011-08-20 19:15:29 [Rampage] Blue.Mary
Subsequence? Consecutive or not?

Ans: Needn't be consecutive as in subsequence of a string...

Last edit: 2011-08-16 06:46:36
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.