#include <bits/stdc++.h>

using namespace std;
long long a,b[1000000],c,d[1000000];


int main()
{
    cin>>c;
    for( long long v=0; v<c; v++)
    {
        cin>>a;
        b[0]=1;
        b[1]=1;
        for(long long i=0; i<=a+2; i++)
        {
            b[i+2]=(b[i]+b[i+1])%1000;
        }
        d[v]=b[a-1];

    }
    for(long long v=0; v<c; v++)
    {
        cout << d[v] << endl;
    }
    return 0;
}