斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……

斐波那契数列是有规律的，我们用 fi 来表示斐波那契数列的第 i 项，则 f₁ = f₂ = 1；当 i > 2 时，f_i = f_i-2 + f_i-1。

现在有 q 次询问，每次询问给你一个整数 n，你需要输出 f_n 除以 1000 的余数。

输入的第一行包含一个整数 q（1 ≤ q ≤ 1000）。

接下来 q 行，每行包含一个整数 n，表示一次询问（1 ≤ n ≤ 1000）。

输出共 q 行，对于每次询问的 n，输出一个整数，表示 fn 除以 1000 的余数。

【样例解释】
· f₂ = 1
· f₅ = 5
· f₇ = 13
· f₁₂ = 144
· f₂₅ = 75025，其除以 1000 的余数为 25。

 提高A