## 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```

hide comments -_-: 2013-05-21 13:35:18 i dont know why i am getting wrong ans.. checked many cases.. pls check dis code http://www.spoj.com/submit/CUBEFR/id=9312881 Santiago Palacio: 2013-02-02 18:10:58 Jmm... scanf must be used for this one. 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

 Added by: Muhammad Ridowan Date: 2011-06-14 Time limit: 0.100s-0.939s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 Resource: Own. For alternate thanks Sayef Azad Sakin