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