# Fibonacci sequence

Description

In mathematics, the **Fibonacci sequence** are the numbers in the following integer sequence:

**0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...**

By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two.

In mathematical terms, the sequence *F _{n}* of Fibonacci numbers is defined by the recurrence relation

*F _{n}* =

*F*+

_{n-1}*F*

_{n-2}with seed values

*F1* = 0, *F2* = 1

The Fibonacci sequence is named after Leonardo Fibonacci. His 1202 book *Liber Abaci* introduced the sequence to Western European mathematics, although the sequence had been described earlier in Indian mathematics.

In this problem, your job is to caculate the F_{i} last 7 digits.

Input

The first line contain one integer N, the number of test case.

The following N lines, each line contain one integer i, means the F_{i}'s last 7 digits which you need to output.( 1 ≤ i ≤ 1000000 )

Output

Output N results. Each in one line.

Sample Input

4 5 6 7 10

Sample Output

3 5 8 34

Source

Editor