Last three digits of the integer part

For each n up to 2e9, report the last three digits of the integer part of (3+sqrt(5))^n, zero padded to three digits.

Medium7MathNumber theoryMatrixDivide and conquerNo attempts yetTime limit2sMemory limit512 MB

Description

Examples3

Problem

Find the last three digits of the integer part of $(3+\sqrt{5})^n$ .

For example, with $n = 5$ , $(3+\sqrt{5})^5 = 3935.73982\ldots$ , so the answer is 935.

If the integer part has fewer than three digits, pad it with leading zeros so the answer always has three digits. For example, with $n = 2$ , $(3+\sqrt{5})^2 = 27.4164079\ldots$ , so the answer is 027.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 100$ ).

Each of the next $T$ lines contains one natural number $n$ ( $2 \le n \le 2 \times 10^9$ ).

Output

For each test case, print the answer on one line in the form Case #c: x. Here $c$ is the test case number, counted from 1, and $x$ is the answer for that test case. Always write $x$ with three digits.