12925번 - Numbers

\( (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 ≤ 2×10⁹)

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