斐波那契数列取模计算

题目描述

斐波那契数列的定义为：数列的第一个和第二个数都为 $1$，从第三个数开始，每个数都等于前两个数之和。现在给定一个正整数 $a$，需要计算斐波那契数列中第 $a$ 个数对 $1000$ 取模的结果。

输入格式

• 第一行包含一个整数 $n$，表示测试数据的组数。
• 接下来 $n$ 行，每行包含一个正整数 $a$（$1 \leq a \leq 1000000$），代表要查询的斐波那契数列的项数。

输出格式

输出 $n$ 行，每行对应一个输入的结果。每行输出一个正整数，即斐波那契数列中第 $a$ 个数对 $1000$ 取模的结果。

样例

样例输入

4
5
2
19
1

样例输出

5
1
181
1