## PRIME1 - Prime Generator

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

### Input

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.

### Output

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.

### Example

Input:2 1 10 3 5Output:2 3 5 7 3 5

**Warning: large Input/Output data, be careful with certain languages (though most should be OK if the algorithm is well designed)**

### Information

After cluster change, please consider PRINT as a more challenging problem.Added by: | Adam Dzedzej |

Date: | 2004-05-01 |

Time limit: | 6s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: NODEJS PERL6 |