P15910 [TOPC 2024] 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^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^n}}$, the $7^{7^n}$-th Fibonacci number. **Note** The Fibonacci sequence is defined as: - $F_0 = 0$ - $F_1 = 1$ - $F_k = F_{k-1} + F_{k-2}$ for $k \ge 2$

The first 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 containing the last $10$ digits of $F_{7^{7^n}}$.

- $1 \le t \le 20$ - $1 \le n \le 10^9$