#include <bits/stdc++.h> using namespace std; int main() { long int i,j,n,s,t; scanf("%ld",&t); while (t--) { scanf("%ld",&n); i=j=1; s=0; while (i<=n) { s=s+j; j=j+2; i++; } printf("%ld\n",s%10000); } return 0; }