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