Problem H
A Research Problem
Input: Standard Input
Output: Standard Output
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 Euler’s 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.
|
integer n |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|
phi(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:
According to
this formula 
.
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 phi_n (1≤phi_n≤100000000). Input is terminated by a line where phi_n=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 phi_n 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)=phi_n. 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 Output for Sample Input
1224228096050000000 |
Case
1: 12 13 Case
2: 24 35 Case
3: 2280960 2283989 Case
4: 5000000 6265625 |
Problem setter: Shahriar Manzoor