Its world war Z and you are a member of the secret crypto-society. Your team has intercepted an important piece of cryptic document from enemies. In order to decipher the document you need a set of prime numbers as they are an integral part of any modern cryptosystem.

Given a range, find the total number of prime numbers inclusive in that range and help stop the war.

Input:
The input begins with the number t of test cases in a single line (t ≤ 10). In each of the next lines
there are two numbers m and n (1 ≤ m ≤ n ≤ 100000000) separated by a space.

Output:
For every test case print all prime numbers p such that m ≤ p ≤ n, one number per line.

(watch out for larger range)

SAMPLE INPUT
3
1 10
100 10000
10000 10000000

SAMPLE OUTPUT
4
1204
663350

见题面

见题面