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 ≤ 1018). 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 4 10 87 3456 1000000000 0 Sample Output Case 1: 3 Case 2: 5 Case 3: 21 Case 4: 233 Case 5: 1346269