#include<iostream> using namespace std; int main() { int v=1,t,n; long long s=0; cin>>t; while(t--){ cin>>n; for(int i=0;i<n;i++){ s=(v+s)%10000; v=(v+2)%10000; } cout<<s<<endl; s=0; v=1; } return 0; }