피보나치 행운의 수

럭키 777 슬롯 게임에 오신 것을 환영합니다. 이 게임은 복잡한 수학 문제로 유명하며, 잭팟은 가장 똑똑한 사람만 받을 수 있습니다.

슬롯 머신은 신비로운 수열, 즉 피보나치 수열을 바탕으로 동작합니다. 다만 평범한 피보나치 수열이 아닙니다. 슬롯 게임에서 행운을 상징하는 숫자 $7$을 바탕으로 한 변형이 들어 있습니다.

럭키 777 슬롯 머신의 레버를 당기면 정수 $n$과 7의 거듭제곱으로 아주 큰 수 $7^{7^{7^n}}$를 만듭니다. 이 수는 너무 커서 가장 성능 좋은 컴퓨터로도 직접 계산할 수 없습니다.

잭팟을 받으려면 $F_{7^{7^{7^n}}}$, 즉 $7^{7^{7^n}}$번째 피보나치 수의 마지막 10자리를 구해야 합니다.

첫 번째 줄에 테스트 케이스의 개수 $t$가 주어진다. 이어지는 $t$개의 줄에는 각각 양의 정수 $n$이 하나씩 주어진다.

각 테스트 케이스마다 $F_{7^{7^{7^n}}}$의 마지막 10자리를 한 줄에 출력한다.

• $1 ≤ t ≤ 20$
• $1 ≤ n ≤ 10^9$

피보나치 수열은 다음과 같이 정의된다.

• $F_0 = 0$
• $F_1 = 1$
• $F_k = F_{k-1} + F_{k-2}$ ($k ≥ 2$)