# A Research Problem

A mad researcher was trying to get fund for his research project but it is a pity that after a year he was able to collect 500\$ only. So all his research work has gone to ashtray. The mad researcher now wants his revenge, so he wants you to solve his unfinished research problem within a very limited time. You will be happy to know that his research is related to Eulers phi function. Euler’s phi (or totient) function of a positive integer n is the number of integers in {1, 2, 3, . . . , n} which are relatively prime to n. This is usually denoted as φ(n). The table below shows the value of phi function for first few numbers. integern 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 φ(n) 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 Given the value of n, it is very easy to find the value of φ(n) using the formula below: ∏1 (1 − ) // Here p is prime φ(n) = n Accordingtothisformulaφ(12)=φ(22∗3)=12(1−1)(1−1)=12∗1 ∗2 =4. But your task is not quite straightforward, given the value of φ(n) you will have to find the minimum possible value of n. Input The input file contains at most 100 lines of input. Each line contains a positive integer phin (1 ≤ phin ≤ 100000000). Input is terminated by a line where phin = 0. This line should not be processed. Output For each line of input produce one line of output. This line contains the serial of output followed by two integers phin and n. The first integer is the integer taken as input and the second integer is the minimum possible value of n, for which φ(n) = phin. All the input numbers will be such that for all given input there will be a possible value of n less than 200000000. Sample Input 12 24 2280960 5000000 0 Sample Output Case 1: 12 13 Case 2: 24 35 Case 3: 2280960 2283989 Case 4: 5000000 6265625 p|n p 2323