#include #include

using namespace std;

int n,a[10000],t;

int hs(int x){

if(a[x])return a[x];

else if(x<=2){

a[x]=1;
	
return a[x];
}

else{

a[x]=hs(x-1)%1000+hs(x-2)%1000;
	
return a[x];

}

}

int main(){

cin>>n;

for(int i=1;i<=n;i++){

cin>>t;
	
cout<<hs(t)<<endl;

}

return 0;

}