Problem E
Partitioning a Number
Input: Standard Input

Output: Standard Output

let f(n) be the number of ways to write n as a sum of powers of 2. Each power can be used at most twice For example, there are five ways to partition 10:

8+2 8+1+1 4+4+2 4+4+1+1 4+2+2+1+1

So we have f(10)=5.

Given n, find the maximal value among f(0),f(1),...,f(n).

Input

The input contains at most 1000 test cases. Each test case contains a single line containing an integer n (1 ≤ n ≤ 10¹⁸). The last test case is followed by a single zero, which should not be processed.

Output

For each test case, print the case number and the maximal value from f(0) to f(n). Look at the output for sample input for details.

Sample Input Output for Sample Input

4 10 87 3456 1000000000 0

Case 1: 3 Case 2: 5 Case 3: 21 Case 4: 233 Case 5: 1346269

---

Problemsetter: Linyun Yu

Special thanks: Rujia Liu