# Fibonacci sequence

1000ms    65536K
728    184
Easier

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

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 Fi'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

keefo on 2014-01-09 18:32:21