Fibonacci Lucky Numbers

Welcome to the Lucky 777 Slot Game! This game is known for its complex mathematical challenges, where only the smartest can win the jackpot.

The slot machine is powered by a mysterious sequence—the Fibonacci sequence. But it’s no ordinary Fibonacci sequence; it has a twist inspired by the number $7$, the symbol of luck in slot games.

When you pull the lever of the Lucky 777 Slot Machine, it generates a gigantic number using an integer $n$ and the power of sevens: $7^{7^{7^n}}$. This number, however, is so massive that even the most powerful computers cannot handle it directly.

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

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

For each test case, output one line contains 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$