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