Description

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

Given a positive integer a, find the result of the a-th Fibonacci number modulo 1000.

Input Format

The first line contains an integer n, representing the number of test cases. The following n lines each contain a positive integer a (1 ≤ a ≤ 1,000,000).

Output Format

Output n lines, each corresponding to an input. Each line should contain a positive integer, which is the result of the a-th Fibonacci number modulo 1000.

4
5
2
19
1

5
1
181
1