Fibonacci Lucky Numbers

Welcome to the Lucky 777 Slot Game! This game is known for its complex math problems, and only the smartest players win the jackpot.

The slot machine runs on a mysterious sequence, the Fibonacci sequence. It is not the ordinary version, though. The twist is based on the number $7$, the symbol of luck in slot games.

When you pull the lever on the Lucky 777 Slot Machine, it generates a huge number from an integer $n$ and a power of sevens: $7^{7^{7^n}}$. This number is too large for even the most powerful computers to handle directly.

To claim the jackpot, you must compute the last $10$ digits of $F_{7^{7^{7^n}}}$, the $7^{7^{7^n}}$-th Fibonacci number.

The first line contains an integer $t$, the number of test cases. Each of the following $t$ lines is one test case and contains exactly one positive integer $n$.

For each test case, output one line with the last $10$ digits of $F_{7^{7^{7^n}}}$.

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

The Fibonacci sequence is defined as:

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