(3 + √5)^n의 마지막 세 자리

양의 정수 $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$는 1부터 시작하는 테스트 케이스 번호이고, $Y$는 $(3 + \sqrt{5})^n$의 소수점 앞 마지막 세 자리다. 소수점 앞 정수 부분이 세 자리보다 짧으면 앞에 0을 채워서 항상 정확히 세 자리를 출력한다.

• $1 \le T \le 100$
• $2 \le n \le 2000000000$