P13459 [GCJ 2008 #1A] 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\dots$ The answer is $935$. For $n = 2$, $(3 + \sqrt{5})^2 = 27.4164079\dots$ The answer is $027$.

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

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.

**Limits** - $1 \leq T \leq 100$ **Small dataset (15 Pts, Test set 1 - Visible)** - $2 \leq n \leq 30$ **Large dataset (35 Pts, Test set 2 - Hidden)** - $2 \leq n \leq 20000000000$