#include <iostream> #include <algorithm> #include <vector> #include <string> #include <math.h> using namespace std; int main() { int t, s, v; cin >> t; while (t--) { int n; cin >> n; s = 0; v = 1; for (int i = 0; i < n; i++) { s = (s+v)%10000; v = v + 2; } printf("%d\n", s); } return 0; }