prime generator with less complexity and less memory

In this problem you have to print all primes from given interval.

Input

t - the number of test cases, then t lines follows. [t <= 150]

On each line are written two integers L and U separated by a blank. L - lower bound of interval, U - upper bound of interval, [2 <= L < U <= 2147483647] [U-L <= 1000000].

Output

For each test case output must contain all primes from interval [L; U] in increasing order.

Example

Input:

2

2 10

3 7

Output:

2

3

5

7

3

5

7