Pawan has a deep love for prime numbers but he is too lazy.

He has been assigned a task to find the total number of primes in a given range. Pawan is getting late to complete the job and ask for your help. Can you?

Input

The first line of the test case contains an Integer T, denoting number of test cases. The following T lines contains 2 Integers a,b each.

Output

Print number of prime in the given range [a,b].

Constraints

1<=T<=10^3

1<=a<=b<=10^5