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 2\,000\,000\,000~.

Sample Input

2
5
2

Sample Output

Case #1: 935
Case #2: 027