#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; //同余原理：b=b+a;b%10000=(b%10000+a%10000)%10000; //19998%10000=(9999%10000+9999%10000)%10000 a=(a+2)%10000; } cout<<b<<endl; } return 0; }