素数距离问题

时间限制：3000 ms | 内存限制：65535 KB

难度：2

描述

现在给出你一些数，要求你写出一个程序，输出这些整数相邻最近的素数，并输出其相距长度。如果左右有等距离长度素数，则输出左侧的值及相应距离。

如果输入的整数本身就是素数，则输出该素数本身，距离输出0

输入

第一行给出测试数据组数N(0<N<=10000)

接下来的N行每行有一个整数M(0<M<1000000)，

输出

每行输出两个整数 A B.

其中A表示离相应测试数据最近的素数，B表示其间的距离。

样例输入

3

6

8

10样例输出

5 1

7 1

11 1-Primes distance problem

Time Limit: 3000 ms | Memory Limit: 65535 KB

Difficulty: 2

Descr iption

You are given a couple, ask you to write a program that outputs these integers nearest neighbor primes, and the output of its length apart. If there are equidistant about the length of a prime number, and the corresponding output value from the left.

If the integer input is itself a prime number, then the output of the primes itself from output 0

Enter

The first line gives the number of test data sets N (0 <N <= 10000)

The next N lines contains an integer M (0 <M <1000000),

Export

Each line of the output of two integers A B.

Wherein A represents a corresponding test data from the nearest prime number, B is the distance therebetween.

Sample Input

3

6

8

10 Sample Output

51

71

111