Description

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$

Input Format

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$.

Output Format

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

5
1
2
3
4
5

1353646637
3172443437
2364206637
9010523437
9481646637

Hint

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