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

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