描述

菲波那契数列定义如下：

• 数列的第 $1$ 项和第 $2$ 项均为 $1$；
• 从第 $3$ 项开始，每一项等于前两项之和。

给定一个正整数 $a$，请你计算菲波那契数列中第 $a$ 项对 $1000$ 取模后的结果。

格式

输入

• 第一行包含一个整数 $n$，表示测试数据的组数。
• 接下来 $n$ 行，每行包含一个正整数 $a$（$1 \le a \le 10^6$）。

输出

• 输出 $n$ 行，每行输出对应输入的结果。
• 输出应为一个正整数，表示菲波那契数列第 $a$ 项对 $1000$ 取模得到的结果。

样例

输入1

4
5
2
19
1

输出1

5
1
181
1