#include<iostream> using namespace std; int main(){ int t; cin>>t; for(int i=1;i<=t;i++){ int n; cin>>n; int a=1,b=0; for(int j=1;j<=n;j++){ b=(a%10000+b%10000)%10000; a=(a+2)%10000; } cout<<b<<endl; } return 0; }