Prime land is a famous city of Wonderland. In primeland most of the people are mathematician. They are very much interest in Prime number. Prime number are those number which only divisible by 1 and Own. So 1 is not a prime number. They know all the prime generate theory of Eratosthenes, Pythagoras, Fermat, Diophantus, Furko, Gauss and so on. However, his favorite one is Euler. The only thing Witua likes more than Euler is Euler’s totient function φ.  But with those theory the can generate only 16th digit prime. Now They want to generated more digit prime number.

Using those theory I know you can generate 18 digit (less than 10^18) prime number which is satisfy the primeland people. So please Help the primeland people.

Given a long  integer number. You should print the next prime number. If he given number is prime just print it. It is satisfy that all the given Integer have a next prime under 10^18.

Input:

Input starts with an integer T (≤ 1000), denoting the number of test cases. Next line given a positive Integer Number N. 0 ≤ N ≤ 10^18

Output:

For each test case, print the case number and the next prime number.

Sample: