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
Jay Pandya: 2011-06-27 08:43:30

yeah..may be shukla is right...otherwise this one is really easy

Ikhaduri: 2011-06-23 12:37:23

I don't get what's wrong with my code. It should be getting TLE not WA.
RE: got where i'm wrong

Last edit: 2011-06-24 06:10:21
kanishka: 2011-06-20 21:35:57

i dont know why m getting wrong ans.....
no need to pre compute....just chek till 100^3 if it divides n.....
that means loop will run for just 100 times....
correct me if m wrong??


EDIT:got it wher im wrong...

Last edit: 2011-06-21 12:56:55
karthikeyan: 2011-06-17 04:33:41

@shukla: ter is enough room to pre process ;)

Muhammad Ridowan: 2011-06-16 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: 2011-06-16 11:08:41

Are you sure that time limit for some test case are 0s? :|

Suprabh Shukla: 2011-06-16 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 pre-computation is made impossible ...

AJAY: 2011-06-15 15:28:10

am getting time limit exceeded :( pls help!!

Filip Ice: 2011-06-14 17:24:29

more test cases please, getting wrong answer..


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