Description
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。
给出一个正整数x，要求菲波那契数列中第x个数对1000取模的结果是多少。（就是计算除以1000的余数）
Input
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数x
(1 <= x <= 1000000)。
(1<=n<=10000)
Output
n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第x个数对1000取模得到的结果。
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