숫자 (작은 입력)

양의 정수 $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$이 하나씩 주어진다.

제한

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

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

Case #X: Y

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