CUBNUM  Cube Numbers
For any positive integer n, n can be represented as sum of other positive cube numbers (n=a_{1}^{3}+a_{2}^{3}+...+a_{m}^{3}). Your task is to print the smallest m, where m is number of cube numbers used to form n, such that n=a_{1}^{3}+a_{2}^{3}+...+a_{m}^{3}. For example:
 n=5,n=1^{3}+1^{3}+1^{3}+1^{3}+1^{3} (m=5)
 n=8,n=2^{3} (m=1)
 n=35,n=2^{3}+3^{3} (m=2)
Edit: My fastest time is 0.05s now lol
My Java solution is also accepted.
Input
Input consists of several test cases separated by new lines. Each test case consists of a positive integer, denoting the number of n (1 ≤ n ≤ 10^{5}). Input is terminated by end of file (EOF).
It is guaranteed that total test case per input file is less than 10^{5}.
Note: For c++ users, you can use while(scanf("%d",&n)!=EOF); to read input until EOF.
Warning: large Input/Output data, be careful with certain languages!.
Output
For each case, print "Case #X: M", where X (1 ≤ X ≤ 10^{5}) is the case number,and M is the minimum cube numbers used to form the integer n. There must be no trailing spaces at the end of printed lines, neither empty characters. Print a newline after each testcase.
Example
Input: 1 2 5 8 35 Output: Case #1: 1 Case #2: 2 Case #3: 5 Case #4: 1 Case #5: 2
hide comments
divyansh_soni:
20180921 20:51:26
i tried binary_search(greedy)+dp ,but failed at test 10.


urimaj:
20180809 08:56:08
good dp problem!! 

jakshat_desai:
20180325 14:03:58
The value of the number for which the sum is to be found is always less than 10^5 right? 

kspoj:
20171122 15:36:33
I'm getting WA at testcase #10 :(


aditya_rev:
20171118 22:03:41
Precompute should works. But why getting WA ? :(


draco_malfoy:
20170927 17:16:19
@hanstan can you please help me with my solution no 20241014?Getting WA.


rayhan50001:
20170814 13:35:34
Cbrt cost me 3 WA.


namitp:
20170813 12:56:19
Very Easy Nailed It in one Go.... 

viratian_070:
20170702 21:30:32
please dont use cbrt function...gave me 10 wa's


sandeep_4141:
20170620 06:44:37
precompute may save you!! 
Added by:  hanstan 
Date:  20160621 
Time limit:  0.200s3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  Self 