F. Fibonacci Lucky Numbers
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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.

Input

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

Technical Specification

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

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

Example
Input
5
1
2
3
4
5
Output
1353646637
3172443437
2364206637
9010523437
9481646637
Note

The Fibonacci sequence is defined as:

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