수

이 문제에서는 수 (3 + √5)^{n}의 소수점 앞 마지막 세 자리를 구해야 한다.

예를 들어 n = 5일 때, (3 + √5)^{5} = 3935.73982...이다. 답은 935이다.

n = 2일 때, (3 + √5)^{2} = 27.4164079...이다. 답은 027이다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100

작은 데이터 세트 (테스트 세트 1 - 공개)

2 ≤ n ≤ 30

큰 데이터 세트 (테스트 세트 2 - 비공개)

2 ≤ n ≤ 2000000000

입력의 첫 줄에는 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 각각 별도의 줄에 주어진다. 각 테스트 케이스에는 양의 정수 n 하나가 주어진다.

각 입력 케이스마다 다음을 출력한다.

Case #X: Y

여기서 X는 테스트 케이스 번호이고, Y는 수 (3 + √5)^{n}의 마지막 세 정수 자리이다. 이 수의 정수 자릿수가 세 자리보다 적으면, 출력이 정확히 세 자리를 포함하도록 앞에 0을 추가한다.