Last three digits of (3 + √5)^n

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

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

The first line holds the number of test cases $T$.

Each of the next $T$ lines holds one positive integer $n$.

For each test case print one line in this format.

Case #X: Y

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

• $1 \le T \le 100$
• $2 \le n \le 2000000000$