#include<iostream>
using namespace std;
int Mod = 10007;
int GetMod(long int n,int value) 
{
	int result=1;
	if(n==1) return (result*value)%Mod;
	while(n>1)
	{
		if(n%2==1){
			result = (result*value)%Mod;
			n -= 1;
		} else {
			result = (result*value*value)%Mod;
			n /= 2;
		}
	}
	return result;
}
int main()
{
	
	int cases,rel;
	long int n;
	scanf("%d",&cases);
	while(cases--)
	{
		scanf("%ld",&n);
		rel = (GetMod(n-1,2)+GetMod(n-1,4))%Mod;
		printf("%d\n",rel);
	}
	
	return 0 ;
}