Blocks on Blocks

If you know the game “tetris”, you may be familiar with the following figures: These figures contains rows of squares. In each row, squares are consecutive. Adjacent rows share at least one side of a square, so the following figures are not allowed: Given the number of squares, count the number of figures. Since the number may be huge, you may only print the lower 4 DIGITS if the answer exceeds 9999, otherwise print out every significant digit of the number. Input The first line of input contains a single integer t (1 ≤ t ≤ 20), the number of test cases. Each test case contains a single integer n (1 ≤ n ≤ 1, 000, 000, 000), the number of squares. Output For each test case, print out the case number of your answer followed by the required number or digits as described in the problem statement. Sample Input 3 3 5 7 Sample Output Case 1: 6 Case 2: 61 Case 3: 629