숫자 (작은 입력)

n이 30 이하로 작을 때 (3+√5)^n의 정수 부분 마지막 세 자리를 구해 Case #X: Y 형식으로 출력한다.

보통4수학정수론구현아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제 설명

예제4

양의 정수 $n$ 에 대해 $(3+\sqrt{5})^n$ 의 소수점 앞 마지막 세 자리를 구한다.

예를 들어 $n = 5$ 이면 $(3+\sqrt{5})^5 = 3935.73982\ldots$ 이므로 답은 935다. $n = 2$ 이면 $(3+\sqrt{5})^2 = 27.4164079\ldots$ 이므로 답은 027이다.

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어지는 $T$ 개의 줄에 각각 양의 정수 $n$ 이 하나씩 주어진다.

제한

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Case #X: Y

$X$ 는 테스트 케이스 번호이고, $Y$ 는 $(3+\sqrt{5})^n$ 의 정수 부분에서 마지막 세 자리다. 정수 부분이 세 자리보다 짧으면 앞에 0을 채워 정확히 세 자리로 출력한다.