#include <bits/stdc++.h> using namespace std; int t; int s; long long int n; int dq; int main() { cin >> t; for(int i=1;i<=t;i++) { dq=1; n=0; cin >> s; for(int i=1;i<=s;i++) { n+=dq; dq+=2; } cout << n%10000 << endl; } return 0; }