## 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``` agralalarocks: 2016-07-26 22:49:19 Could someone please take a look at my code its VAKNIg on ideone hmp: 2016-07-05 03:08:52 why same code giving compilation error with C++14 and AC with C++4.3.2 praval_singhal: 2016-06-03 20:55:44 First the very first Time used lower_bound. Got AC :) Subhendu Sethi: 2016-05-21 03:04:32 No need to Prime Factorize. Think about sieving! Easy. mohitgupta07: 2016-05-13 22:36:02 dun knw why getting wrong answer -_- can anyone tell me dat how many cube free no.s lie in this range!! ysn: 2016-05-02 15:04:45 @Sarthak Munshi 9 is a perfect square not a cube number. you are confusing addition with multiplication. 3+3+3=9 is not a cube number but 3*3*3=27 is a cube number. Edit: it looks like you have already solved the problem. so my comment might be irrelevant to you. can you please reply to my comment? its right under your question Last edit: 2016-05-02 15:09:30 Sarthak Munshi: 2016-05-02 12:09:30 How can 18 be a cube free number ? 9 is a divisor of 18 and it is a cube . ysn: 2016-04-12 13:38:29 @Muhammad Ridowan i wrote a code that doesnt even use a loop. but still i am getting TimeLimit exceeded. Why? Setter ans: Java scanner is very slow. Use faster input methods Last edit: 2016-06-03 13:20:46 ALi Ibrahim: 2016-04-10 22:26:35 My 50th on Spoj :D pvsmpraveen: 2016-01-29 20:03:39 Cutest lowerbound ever