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