Limits
8s, 512 MB
Peter loves numbers. But he does not like powers of the numbers. Like he loves 2 but does not like 4(which is a power of 2). He defines powerless numbers as numbers which are don’t divisible by any power of another number. Like 2,3,5,6,7,10,11,13 etc. 250 is not a powerless number as it is divisible by 125 ( 555). Now he created an array of first 10^13 (10000000000000) numbers. Then he gives that to me to store. But I don’t have enough space in my computer to store it. So I need your help!
Input
Input starts with an integer T (<=200). Then T lines follow. On each T lines there will be a number N ( 1<= N <= 10^13).
Output
For each N, you have to print the Nth powerless number.
Sample
| Input | Output |
|---|---|
10 1 2 3 4 5 6 7 8 9 10000000000000 | Case 1: 1 Case 2: 2 Case 3: 3 Case 4: 5 Case 5: 6 Case 6: 7 Case 7: 10 Case 8: 11 Case 9: 13 Case 10: 16449340668746 |
