NAJPLNP - Prime Land and Next Prime number

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:

Input

Output

6
1
2
10
20
100
1000000

Case 1: 2
Case 2: 2
Case 3: 11
Case 4: 23
Case 5: 101
Case 6: 1000003

 

 


Added by:Najmuzzaman
Date:2014-10-25
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-10-26 19:23:32 [Lakshman]
I think number of test case should be at least 500 to 1000, 100 is very small.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.