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)