1346：斐波那契数列
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：2
解决：2
题目描述
斐波那契数列是指这样的数列：数列的第一个和第二个数都为 $1$，接下来每个数都等于前面 $2$ 个数之和。
给出一个正整数 $a$，要求斐波那契数列中第 $a$ 个数对 $1000$ 取模的结果是多少。
给出一个正整数 $a$，要求斐波那契数列中第 $a$ 个数对 $1000$ 取模的结果是多少。
输入
第 $1$ 行是测试数据的组数 $T$，后面跟着 $T$ 行输入。
每组测试数据占 $1$ 行，包括一个正整数 $x(1\le x\le 10^6)$，表示要求斐波那契数列的第 $x$ 项。
每组测试数据占 $1$ 行，包括一个正整数 $x(1\le x\le 10^6)$，表示要求斐波那契数列的第 $x$ 项。
输出
输出共 $T$ 行，每行对应一个输入。
样例输入-1 复制
4
5
2
19
1样例输出-1 复制
5
1
181
1