Numbers (Small)

Time limit5sMemory limit512 MB

Summary

Given small n up to 30, print the last three digits of the integer part of (3 + sqrt(5))^n, formatted as Case #X: Y.

Level: Medium4 of 10
Topics: Math, Number theory, Implementation
Solved: No attempts yet

Problem

For a positive integer $n$ , find the last three digits before the decimal point of $(3+\sqrt{5})^n$ .

For example, if $n = 5$ then $(3+\sqrt{5})^5 = 3935.73982\ldots$ , so the answer is 935. If $n = 2$ then $(3+\sqrt{5})^2 = 27.4164079\ldots$ , so the answer is 027.

Input

The first line contains the number of test cases $T$ . Each of the next $T$ lines contains one positive integer $n$ .

Limits

$1 \le T \le 100$
$2 \le n \le 30$

Output

For each test case, print one line in the following format.

Case #X: Y

Here $X$ is the number of the test case and $Y$ is the last three digits of the integer part of $(3+\sqrt{5})^n$ . If the integer part has fewer than three digits, pad it with leading zeros so that the output has exactly three digits.

Examples4

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

Example 2

Input

Expected output

Case #1: 047
Case #2: 055
Case #3: 095
Case #4: 027
Case #5: 647

Example 3

Input

Expected output

Case #1: 935
Case #2: 935
Case #3: 935
Case #4: 935

Example 4
Input
```
2
3
4
```
Expected output
```
Case #1: 143
Case #2: 751
```