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 Fn of Fibonacci numbers is defined by the recurrence relation
Fn = Fn-1 + Fn-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 Fi last 7 digits.
The first line contain one integer N, the number of test case.
The following N lines, each line contain one integer i, means the Fi's last 7 digits which you need to output.( 1 ≤ i ≤ 1000000 )
Output N results. Each in one line.
4 5 6 7 10
3 5 8 34