Explanation

The Fibonacci sequence refers to a sequence in which the first and second numbers are both 1, and each subsequent number is equal to the sum of the first two numbers. Given a positive integer a, what is the result of modulo 1000 for the a-th number in the Fibonacci sequence.

Input format

The first line is the number of test data groups n, followed by n lines of input. Each set of test data occupies one row and includes a positive integer a (1 ≤ a ≤ 1000000).

Output format

N rows, with each row corresponding to an input. The output should be a positive integer, which is the result obtained by multiplying the a-th number in the Fibonacci sequence by 1000.

Example

4
5
2
19
1

5
1
181
1