题目描述

斐波那契数列 F1=F2=1，输出指定项对 1000 的余数。

输入格式

第一行测试组数，随后每行一个 a。

输出格式

每组输出一行。

样例

4
5
2
19
1

5
1
181
1

数据范围

1≤组数≤100，1≤a≤1000000。