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 Specification

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$.

Output Specification

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

Time limit: 30 seconds per test set.

Memory limit: 1 GB.

$1\le T\le 100$.

Small Dataset

$2\le n\le 30$.

Large Dataset

$2\le n\le 2000000000$.

Sample Input

2
5
2

Sample Output

Case #1: 935
Case #2: 027