#include <bits/stdc++.h> using namespace std;

int n, a[1000005], x ;

int main() { cin >> n; a[1] = 1; a[2] = 1; for (int i = 3; i <= 1000000; i++) { a[i] = (a[i - 1] + a[i - 2]) % 1000; } for (int j = 0; j < n; j++) { cin >> x; cout << a[x] << endl; }

return 0;

}