( (3+\sqrt5)^n )의 정수부의 마지막 3자리를 구하시오.</p>

예를 들어, n = 5인 경우, ( (3+\sqrt5)^5 = 3935.73982... ) 이므로, 답은 935이다.

만약 자릿수가 3자리 이하이라면 leading zero를 붙여 출력한다.

예를 들어, n = 2인 경우, ( (3+\sqrt5)^2 = 27.4164079... ) 이므로, 답은 027이다.

입력 형식

첫 번째 줄에는 Test Case의 개수 T (1 ≤ T ≤ 100)이 입력으로 주어진다.</p>

각 Test Case에는 자연수 n이 하나 주어진다. (2 ≤ n ≤ 2×10⁹)

출력 형식

각 Test case에 대해, “Case #c: x”의 형식으로 각 줄에 정답을 출력한다. c는 Test Case의 번호이다. (1부터 매겨진다.) x는 해당 Test Case의 정답이다.

예제 입력

2
5
2

예제 출력

Case #1: 935
Case #2: 027