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: 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 ....

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 ...


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