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

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


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