Problem
In this problem, you have to find the last three digits before the decimal point for the number (3 + √5)^{n}.
For example, when n = 5, (3 + √5)^{5} = 3935.73982... The answer is 935.
For n = 2, (3 + √5)^{2} = 27.4164079... The answer is 027.
Input
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
For each input case, you should output:
Case #X: Ywhere X is the number of the test case and Y is the last three integer digits of the number (3 + √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 <= T <= 100
Small dataset
2 <= n <= 30
Large dataset
2 <= n <= 2000000000
Sample
Input 
Output 
2

Case #1: 935

Points  Correct  Attempted 

15pt  577  1925 
35pt  96  364 