Frankfurt UAS Exercises Week 4 DUPLICATE

Start

2018-05-10 18:00 UTC

Frankfurt UAS Exercises Week 4 DUPLICATE

End

2018-05-17 18:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -315 days 20:51:37

Time elapsed

168:00:00

Time remaining

0:00:00

Problem F
Blocks on Blocks

If you know the game tetris, you may be familiar with the following figures:

\includegraphics{blocks1}

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:

\includegraphics{blocks2}

Given the number of squares, count the number of figures. Since the number may be huge, the answer is the number of figures modulo $10000$. That is, the output will always be between $0$ and $9999$.

Input

The first line of input contains a single integer $t$ ($1\le t \le 100$), the number of test cases. Each test case contains a single integer $n$ ($1 \le n \le 1\, 000\, 000\, 000$), the number of squares.

Output

For each test case, print the case number followed by the answer for that case. Use the format in the sample output below.

Sample Input 1 Sample Output 1
3
3
5
7
Case 1: 6
Case 2: 61
Case 3: 629