SPOJ Brasil

For any positive integer n, n can be represented as sum of other positive cube numbers (n = a₁³ + a₂³ + ... + a_m³). Your task is to print the smallest m, where m is number of cube numbers used to form n, such that n = a₁³ + a₂³ + ... + a_m³. For example:

• n = 5, n = 1³ + 1³ + 1³ + 1³ + 1³ (m = 5)
• n = 8, n = 2³ (m = 1)
• n = 35, n = 2³ + 3³ (m = 2)

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⁵). Input is terminated by end of file (EOF).
It is guaranteed that total test case per input file is less than 10⁵.

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