On the world of PRos exists different type of numbers but for the our friend Angel there are some special numbers called PRS numbers .

A PRS number is the sum of two different prime numbers that falls in love. For example 5 is a PRS number $(5 = 3 + 2)$ but 4 is not a PRS number.

Angel needs to know how many PRS numbers are between a range $[s, f]$ inclusively.

Input

The first line contains an integer T ( $0 \leq T \leq 100000$ ) representing the number of test cases, the next T lines represent a test case, each test case contains one line with S and F ( $0 \leq S < F \leq 100000$ ).

Output

For each test case print the number of PRS between the range