#include using namespace std; int main(){ int T; cin>>T;

int f[1000010];
f[1]=1;
f[2]=1;
for(int i=3;i<=1000000;i++){
	f[i]=(f[i-1]+f[i-2])%1000;
}
while(T--){
	int x;
	cin>>x;
	cout<<f[x]<<endl;
}
return 0;

}