Last three digits of the integer part

Time limit2sMemory limit512 MB

Summary

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.

Level: Medium7 of 10
Topics: Math, Number theory, Matrix, Divide and conquer
Solved: No attempts yet

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.

Examples3

Example 1
Input
```
2
5
2
```
Expected output
```
Case #1: 935
Case #2: 027
```
Example 2
Input
```
1
2
```
Expected output
```
Case #1: 027
```
Example 3
Input
```
1
2000000000
```
Expected output
```
Case #1: 751
```