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
Xsquare:
20120515 18:12:55
Even my solution can't get WA!!.. checked many test cases.. can be verified by the extreme one too!!..


strings:
20120409 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:
20111209 19:12:32
why it is giving TLE the loop is runnning only 100 times at max .... 

Jay Pandya:
20110627 08:43:30
yeah..may be shukla is right...otherwise this one is really easy 

Ikhaduri:
20110623 12:37:23
I don't get what's wrong with my code. It should be getting TLE not WA.


kanishka:
20110620 21:35:57
i dont know why m getting wrong ans.....


karthikeyan:
20110617 04:33:41
@shukla: ter is enough room to pre process ;)


Muhammad Ridowan:
20110616 14:18:21
@Hakim There is only one test case and thats 3s. Another test case was disable(won't run on submission) and for that I make thats time 0s. However spoj is showing both. 

Lukmanul Hakim:
20110616 11:08:41
Are you sure that time limit for some test case are 0s? : 

Suprabh Shukla:
20110616 10:48:23
Maybe the problem could be made more interesting by increasing the limit on n and decreasing the no. of tests a little so that precomputation is made impossible ... 
Added by:  Muhammad Ridowan 
Date:  20110614 
Time limit:  0.100s0.939s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own. For alternate thanks Sayef Azad Sakin 