#include<bits/stdc++.h>
using namespace std;
int main(){
	int x[1000010]={0},n,d=0,a[1000010];
	x[1]=x[2]=1;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
        if(a[i]>=d)
            d=a[i];
	}
    for(int i=3;i<=d;i++)
        x[i]=(x[i-1]+x[i-2])%1000;
    for(int i=1;i<=n;i++)
        cout<<x[a[i]]<<endl;
	return 0;
}