Description

The Fibonacci sequence is defined as follows: the first and second numbers are both $1$, and each subsequent number is the sum of the previous two numbers. Given a positive integer $a$, find the $a$-th number in the Fibonacci sequence modulo $1000$.

Input Format

The first line contains the number of test cases $n$, followed by $n$ lines of input. Each test case consists of a single line with a positive integer $a$ ($1\leq a\leq 1000000$).

Output Format

Output $n$ lines, each containing the result for the corresponding input. The output should be a positive integer, which is the $a$-th Fibonacci number modulo $1000$.

Sample

4
5
2
19
1

5
1
181
1