题目描述

任务就是帮助生成给定范围内的所有质数。

输入描述

有多组数据。 输入数据第一行是一个整数T，表示测试数据的组数.

输出描述

对于每一组测试数据，输出所有在[m,n]中的质数p，一行一个。 不同测试数据之间用一个空行分隔。

Samples

2
1 10
3 5

2
3
5
7

3
5

数据范围

30%的数据：m<n≤1000；

50%的数据：m<n≤10^6且n-m≤1000；

100%的数据：T≤10，m<n≤10^9且n-m≤10^6。

注意：提交文件大小限制小于3KB。