[Python] 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, 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 , the number of test cases. Each test case contains a single integer , 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.