在一个农场里，兔子繁殖模式如下： 初始时，有一对小兔子（第一个月和第二个月兔子数量都记为 1 对）。从第三个月开始，每个月的兔子对数等于前两个月兔子对数之和。农场主想要知道在这种繁殖模式下，第 a 个月时兔子的对数（对1000取模的结果）是多少，以便合理规划兔舍空间。

从文件 rabbit.in 中读入数据。 第一行是询问的次数 n，后面跟着 n 行输入。每组询问占 1 行，包括一个正整数 a (1 <=a <= 1000000)，代表要查询的月份。

输出到文件 rabbit.out 中。 共 n 行，每行输出对应一个询问。输出应是一个正整数，为第 a 个月兔子对数（对1000取模的结果）。

【样例 1 解释】

第1个月：初始兔子，1对

第2个月：兔子未成熟，1对

第3个月：开始繁殖，1+1=2对

第4个月：1+2=3对

第5个月：2+3=5对

第6个月：3+5=8对

第7个月：5+8=13对

第8个月：8+13=21对

输出结果为每个查询月份对应的兔子对数模1000的结果

测试点100%：n<=1000,a<=1000000