Rar the cat likes fishes and loves to include fishes in his favourite dish, fish soup. Since you all have provided great help and support in handling all the strings, he decided to reward you with the highest quality fish soup.
However, in order to make the highest quality (tastiest) fish soup, he needs fish which can pass through a certain sieve which his ancestors has passed down for generations, known as the sieve of eratosthenes.
By placing fishes on top of the sieve, the fish will be able to pass through the sieve if its weight is of a prime number (Eg. 2kg and 3kg) and sieve out those fishes that are not.
However, Rar the cat is not very smart, and doesn't know the weights of the fish he should be looking out for in the fish market. As such, to guarentee he has at least some fish to cook fish soup, he decides to buy fish of weight Pkg to Qkg inclusive, one each at intervals of 1kg. (Pkg, (P+1)kg, (P+2)kg ... (Q-2)kg, (Q-1)kg, Qkg)
Help Rar the cat calculate how many fishes he can use to cook his much coveted fish soup of the highest quality given P and Q, in terms of kg.
Your program should be able to handle multiple queries.
The first line of input will be a single integer, TC.
The following TC lines of input will consists of one query each.
Each query consists of 2 integers, P and Q which denotes the range of fishes Rar the cat bought.
For 100% of the testcases, 1 ≤ TC ≤ 100000 and 2 ≤ P ≤ Q ≤ 1000000.
For 60% of the testcases, 1 ≤ TC ≤ 10000 and 2 ≤ P ≤ Q ≤ 10000.
For 30% of the testcases, TC = 1 and 2 ≤ P ≤ Q ≤ 1000.
For each query, output a single integer on a line which denotes the number of fishes Rar the cat can use to cook the highest quality fish soup.
Refer to the Sample Output for more details.
For this question only, all the testcases will be made public (you will know your score). Please work on improving it (: