Problem D
Blocks on Blocks
Input: standard input
Output: standard output
Time Limit: 1 seconds

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 Output for Sample Input

3 3 5 7

Case 1: 6 Case 2: 61 Case 3: 629

---

Problem setter: Rujia Liu, EPS

Special thanks: Shahriar Manzoor (For drawing pictures), EA :)