Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!
The input begins with the number t of test cases in a single line. In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.
For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.