Problem H
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 |
