Fibonacci Sequence

Problem Background

Special for beginners, ^_^

Problem Description

The Fibonacci sequence is defined as follows: the first and second numbers are both 1, and each subsequent number equals the sum of the preceding two numbers.

Given a positive integer $a$, what is the value of the $a$-th Fibonacci number modulo $1000$?

Input Format

The first line contains $n$, the number of test cases, followed by $n$ lines of input. Each test case occupies one line and contains a positive integer $a (1 \le a \le 1000000)$.

Output Format

Output $n$ lines, each corresponding to one input. Each line should contain a positive integer — the $a$-th Fibonacci number modulo $1000$.

Sample Input

4
5
2
19
1

Sample Output

5
1
181
1

Constraints

1 second, 1024 KiB for each test case.