12728번 - n제곱 계산 다국어

문제

이 문제에서 숫자 (3 + √5)ⁿ 에 대한 소수점 앞에 마지막 세 자리를 찾아야합니다. 예를 들어, n = 5 일 때 (3 + √5)⁵ = 3935.73982 ... 이므로 답은 935입니다. n = 2 인 경우 (3 + √5)² = 27.4164079 … 이므로, 답은 027입니다.

입력

첫 번째 입력 줄은 테스트 케이스의 수 T를 알려줍니다. 각각의 T 테스트 케이스는 행(라인)이 분할되어 주어지며, 각 테스트 케이스는 하나의 양의 정수 n을 알려줍니다.

출력

각 입력 테스트 케이스에 대해 다음과 같은 출력이 필요합니다.

Case #X: Y

여기서 X는 테스트 케이스 번호이고, Y는 숫자 (3 + (5)^(0.5))^n 의 마지막 세 정수입니다. 만일 소수점 앞의 숫자(정수)가 세 자리보다 작은 경우 출력에 정확히 세 자리가 포함되도록 앞에 0을 추가하십시오.

제한

• 1 ≤ T ≤ 100
• 2 ≤ n ≤ 2000000000

힌트