시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 523 22 20 68.966%

문제

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

입력

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

제한

  • 1 <= T <= 100
  • 2 <= n <= 2000000000

출력

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

Case #X: Y

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

예제 입력

2
5
2

예제 출력

Case #1: 935
Case #2: 027

힌트