斐波波那契数列是指这样的数列: 数列的第一个和第二个数都为 1 ，接下来每个数都等于前面 2 个数之和。 给出一个正整数 a，要求斐波那契数列中第 a 个数对 1000 取模的结果是多少。
第一行T，接下来T行a（1≤a≤1e6）
T行结果
4 5 2 19 1
5 1 181 1
