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