#include<iostream>
#include<stdio.h>
#define ri register int
#define lint long long  
#define MAX 10086001
#define N 1000000
using namespace std;
lint n,t;
lint je[N],ans[N];
int main(){
	std::ios::sync_with_stdio(false);std::cin.tie(NULL);
	je[0]=1;
	for(ri i=1;i<=N;i++)je[i]=je[i-1]*i%MAX;
	for(ri i=1;i<=N;i++)ans[i]=je[(i-1)/2];
	for(ri i=1;i<=N;i++)ans[i]=(ans[i]+ans[i-1])%MAX;
	for(ri i=1;i<=N;i++)ans[i]=(ans[i]+ans[i-1])%MAX;
	for(ri i=1;i<=N;i++)ans[i]=(ans[i]+ans[i-1])%MAX;
	cin>>t;
	for(ri i=1;i<=t;i++){
		cin>>n;
		cout<<ans[n]<<endl;
	}	
	return 0;
}