Let F(x) is a function which returns the last digit of the first prime number with 'x' digit. The first few values of F(x) is:

F(1) = 2
F(2) = 1
F(3) = 1
F(4) = 9
F(5) = 7

The value of F(x) for 1 <= x <= 25 is {2,1,1,9,7,3,3,9,7,7,9,3,9,7,1,7,1,3,3,1,9,7,9,7,7}.

In this task you have to compute the sum up F(x)'s between two given a and b (including)


Constraints:

1 <= T <= 1000
1 <= a <= b <= 1000

Input

The first line of the input is an integer T(say),then T test cases follows.

Output

Output the answer one in each line.

Example

Input:
3
647 997
736 823
632 928

Output:

1741
410
1487

Constraints:

1 <= T <= 1000
1 <= a <= b <= 1000

Score
Score is the length of your code.