## 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``` saket diwakar: 2013-01-17 21:38:52 nice one...:) J.A.R.V.I.S.: 2012-12-10 07:06:27 @Adhityaa 1 divides every number. So if u consider 1 as a cube number then all numbers become cube free Akash Bansal: 2012-10-26 17:41:23 what is the answer for n=99998 and n=999998 Last edit: 2012-10-26 17:42:09 eliminator: 2012-09-29 14:22:19 linear search gives TLE... binary search AC ...... :) Adhityaa: 2012-09-27 08:12:47 How is 1 cube free (1 = 1*1*1) ? vipul gupta: 2012-09-25 05:54:40 can't tell why i am getting WA. please check code no. 7718647 for this problem... i made many test cases and all have given correct answer even the extreme one. please tell. edit: just realised whats wrong.. Last edit: 2012-09-25 06:21:43 Rocker3011: 2012-06-18 03:40:40 a smart precompute is enough for this problem :D Xsquare: 2012-05-15 18:12:55 Even my solution can't get WA!!.. checked many test cases.. can be verified by the extreme one too!!.. please verify if the constraints are correctly mentioned as per the input file! Solution ID: 6994753 strings: 2012-04-09 21:55:23 can't tell why i am getting WA. please check code no. 6816510 for this problem... i made many test cases for myself and all seem to give correct answer. please tell. Kunal Bansal: 2011-12-09 19:12:32 why it is giving TLE the loop is runnning only 100 times at max ....