Description
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。
给出一个正整数a，要求菲波那契数列中第a个数对1000取模的结果是多少。
Input
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a
(1 <= a <= 1000000)。
(1<=n<=10000)
Output
n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数对1000取模得到的结果。
8
7
8
9
10
11
12
8000
10000
13
21
34
55
89
144
125
875
HINT
斐波那契数列
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368