NAJDEC - Destroy Enemy Camp

no tags 

Our Mukti Bahini are doing well. Now they are in a strong position. They know that within a few day they can win the war. Now our commander decides to destroy all the enemy camps (Pak Bahini). All the enemy camping places are in Prime Land. That means the enemy camps are located in positions 2, 3, 5, 7.... Now our Mukti Bahini are in an integer location, and they want to find the next enemy camp to destroy. Please help the Mukti Bahini Commander ‘Bari’ to find the next camp.

You given an integer number. You should print the next prime number (Paki Bahini Camp). If the given number is prime (that mean this place is distroyed by Mukti bahihi or is under control of Mukti Bahini) then print next prime number and the distance of current position. All the given integers have the 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 (enemy camp) and distance from current position.

Example

Input:
6
1
2
10
20
100
1000000

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

hide comments
ice_101: 2023-11-08 05:04:59

I try but face TLE,can anyone give any idea,please?

nadstratosfer: 2018-08-27 23:24:41

AC! Ememy palce is distory.


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