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

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

hide comments
2014-10-29 20:43:41 Kid Algorist
Great optimisations are possible in the problem.
The time limit is definitely too lenient for C/C++,
tweaking just a few lines of code reduced my time from ~2s to 0.01s

Good Problem. |m|

Last edit: 2015-01-12 22:10:43
2014-10-26 05:23:34 Sumit Kumar Rakshit
has nothing to do with the size of n, 1000000 woks fine.. @Sudipto :P
2014-09-21 00:01:05 Nishanth Vijayan
@PurvaBaradia: look at your output carefully :)
2014-08-28 15:05:02 Never see me (saran)
nice question

Last edit: 2014-08-28 17:23:45
2014-08-26 13:48:54 PurvaBaradia
can anyone tell me whats wrong with my code ? it gives wa for 0.45 sec http://ideone.com/gxoqvr
2014-08-13 17:18:18 ****
i used seive. can someone tell me what 's wrong in my code.. i got time limit exceeded.
ID: 12139694

Last edit: 2014-08-14 18:04:36
2014-07-22 07:16:27 « sudipto »
take n<=1000100... it got me AC... n<=1000010 gets WA... :|
2014-05-11 21:29:13 Suraj Rajan
sieve works like a charm...!! :)
2014-02-03 15:18:02 Tarun Garg
No need for b.search ...constraints are too lenient......hashing
2013-08-11 09:59:15 Anant Kumar
Nice and easy problem. Just use sieve and memorization.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.