计算斐波那契数列第a项对1000取模的结果

本题为青少年软件编程（C语言）等级考试三级真题，具体要求如下：

有如下构造规则的数列：第1、2项均为1，后续每项等于前两项之和。给定正整数a，求该数列第a项对1000取模的结果。

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包含一个正整数a（1 ≤ a ≤ 1000000）。

输出共n行，每行对应一个输入的计算结果，为正整数。