PRIME1 - Prime Generator

彼得想为他的密码系统生成一些质数。请帮助他。你的任务是在两个给定的数字之间生成所有的质数。 输入的内容以单行的组数 $t$ 开始， $t \leqslant 10$ 。在接下来的每一行 $t$ 中，都有两个数字 $m$ 和 $n$，其中 $1\leqslant m \leqslant n \leqslant 1000000000, n-m \leqslant 100000$，用空格隔开。 对于每组数据，输出所有质数 $p$ ，使 $m \leqslant p \leqslant n$，每行一个数字，每组数据用空行隔开。

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 (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.

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.

2
1 10
3 5

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](http://www.spoj.com/problems/PRINT/) as a more challenging problem.