정수부의 마지막 세 자리

$(3+\sqrt{5})^n$의 정수부에서 마지막 세 자리를 구한다.

예를 들어 $n = 5$이면 $(3+\sqrt{5})^5 = 3935.73982\ldots$이므로 답은 935이다.

정수부가 세 자리보다 짧으면 앞에 0을 채워 항상 세 자리로 출력한다. 예를 들어 $n = 2$이면 $(3+\sqrt{5})^2 = 27.4164079\ldots$이므로 답은 027이다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 100$)

이어지는 $T$개의 줄에 자연수 $n$이 한 줄에 하나씩 주어진다. ($2 \le n \le 2 \times 10^9$)

각 테스트 케이스마다 한 줄에 Case #c: x 형식으로 답을 출력한다. $c$는 1부터 매기는 테스트 케이스 번호이고, $x$는 그 테스트 케이스의 답이다. $x$는 항상 세 자리로 쓴다.