# Introduction

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

## Constraints

The input begins with the number t of test cases in a single line (t<=10). 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.

``````Input:
2
1 10
3 5

Output:
2
3
5
7

3
5``````

# Approach

We generate prime numbers from 2 to the rightmost possible, but in this case the rightmost entry is huge. We see that the range of numbers denoted by `n - m` can be `Max` (100000).

## Why Square Root or i*i < Max?

Square root of 100 is 10. Let's say a x b = 100, if one number increases the other number decreases.

i.e. 20 x 5 = 100,

We cover this case for 5 that is the numbers less than 10 while finding multiples of 5.

## Steps

We will use this information, and follow the below steps:

1. We can generate the prime numbers from 0 to `Max`.
a. Initialise a boolean array `IsPrime` of size `Max` and set to true
b. We loop from i till `i * i` is less than `Max`
c. Start an inner loop if `IsPrime` is true, from j = `i*i` to `Max` and increment in `i` steps, continue setting to false because it's a multiple.
d. Use the `IsPrime` to generate and return the `PrimeSet` upto `Max`.
2. We generate from Left to Right by using the multiples in the `PrimeSet` obtained in the Step #1
a. Initialise `IsPrime` boolean array for the range and set to true except for `left` set to `1`.
b. find the closest point in the left (first multiple lies in the range) and update the `isPrime` for the subsequent multiples in the range.
c. Print the range by keeping the left as offset.