## CUBEFR - Cube Free Numbers

A cube free number is a number who’s none of the divisor is a cube number (A cube number is a cube of a integer like 8 (2 * 2 * 2) , 27 (3 * 3 * 3) ). So cube free numbers are 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18 etc (we will consider 1 as cube free). 8, 16, 24, 27, 32 etc are not cube free number. So the position of 1 among the cube free numbers is 1, position of 2 is 2, 3 is 3 and position of 10 is 9. Given a positive number you have to say if its a cube free number and if yes then tell its position among cube free numbers.

### Input

First line of the test case will be the number of test case T (1 <= T <= 100000) . Then T lines follows. On each line you will find a integer number n (1 <= n <= 1000000).

### Output

For each input line, print a line containing “Case I: ”, where I is the test case number. Then if it is not a cube free number then print “Not Cube Free”. Otherwise print its position among the cube free numbers.

### Example

```Sample Input:
10
1
2
3
4
5
6
7
8
9
10

Sample Output:
Case 1: 1
Case 2: 2
Case 3: 3
Case 4: 4
Case 5: 5
Case 6: 6
Case 7: 7
Case 8: Not Cube Free
Case 9: 8
Case 10: 9```

 < Previous 1 2 3 4 5 6 7 8 9 Next > monkscoder: 2020-01-20 11:30:05 Take care of formatting... costed me 2 WA sayan_244: 2020-01-18 13:19:11 pair+sieve works krish3d2y: 2019-12-18 17:55:01 Use long long int instead of int, Costed me 2 WA. :( ganeshpc: 2019-11-11 14:42:45 Getting run time error (SIGSEGV), even when my code run for every possible test case on my computer scolar_fuad: 2019-07-15 20:08:01 Fucked after 3rd submission >>>> Little finger is not dead ak67373: 2019-06-14 16:47:20 Last edit: 2019-06-14 17:48:04 prudhvi_495: 2019-06-11 21:26:29 My 125th /^_^\ anshuman16423: 2018-11-30 15:11:50 1 WA in pypy for using slow io functions using xrange and stdin gave AC vibhu04: 2018-10-04 13:29:16 what if we find the prime factors of a number and if the same prime number repeats for more than 2 times then the number will not be cube free?? eg-16 = 2x2x2x2. 2 repeats more than 2 times Last edit: 2018-10-04 13:32:25 samarth1402: 2018-07-08 16:04:46 WA once... in first time I did not read the ques properly. though only perfect cubes are cube free numbers! Corrected this problem in second attempt, finally AC :))