시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 29 13 11 42.308%

문제

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

예를 들어, 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)이 입력으로 주어진다.

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

출력

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

예제 입력 1

2
5
2

예제 출력 1

Case #1: 935
Case #2: 027