PLDGTS - Summing up Last digits

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.




Added by::(){ :|: & };:
Date:2011-04-17
Time limit:21.03s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:A variation of my Mathalon Problem

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.