Don't Show Power

EWU Intra University Prog...
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

InputOutput
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

Submit

Login to submit.

Statistics

75% Solution Ratio
buetpcEarliest, May '18
buetpcFastest, 3058081.8s
buetpcLightest, 33 MB
nmunimShortest, 1075B
Toph uses cookies. By continuing you agree to our Cookie Policy.