# Numbers

In this problem, you have to find the last three digits before the decimal point for the number $(3 + \sqrt {5})^ n$.

For example, when $n = 5$, $(3 + \sqrt {5})^5 = 3935.73982...$. The answer is $935$.

For $n = 2$, $(3 + \sqrt {5})^2 = 27.4164079...$. The answer is $027$.

## Input

The first line of input gives the number of cases, $1 \le T \le 100$. $T$ test cases follow, each on a separate line. Each test case contains one positive integer $2 \le n \le 2\, 000\, 000\, 000$.

## Output

For each input case, you should output: `Case #$X$:
$Y$` where
$X$ is the number of the
test case and $Y$ is the
last three integer digits of the number $(3 + \sqrt {5})^ n$. In case that
number has fewer than three integer digits, add leading zeros
so that your output contains exactly three digits.

Sample Input 1 | Sample Output 1 |
---|---|

2 5 2 |
Case #1: 935 Case #2: 027 |