#include <bits/stdc++.h>
using namespace std;
int book[1000000+5]; //创建一个列表来存变量 
int f(int x)//递归算一下 
{
	if(book[x]!=-1)
		return book[x];
    if (x == 1)//因为题目要求，把0改成1 
        return 1;
    if (x == 2)
        return 1;
    book[x] = (f(x - 1) + f(x - 2))%1000;//这个是那个记忆化 
    return book[x];
}
int main()
{
	for(int i=1;i<=1000000;i++)//按照题目要求出另外几个输出数据 
		book[i] = -1; 
    int n;
    int T;
    cin>>T;
    for(int i=1;i<=T;i++){
	    cin >> n;
    	cout << f(n) % 1000 << "\n";
	}
	return 0;
}