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