#include<cstdio>
#define mod 666013

using namespace std;

//frec vine de la functie recursiva, nu va ganditi la prostii

void frec(long long n, long long p, long long &rez1, long long &rez2)
{
  long long a, b, c, d = n >> 1;;
  if(n == 1)
  {
	rez1 = 1;
	rez2 = 2;
	return ;
  }
  if(n == 2)
  {
	rez1 = 2;
	rez2 = 1;
	return ;
  }
  if(n & 1)
  {
	c = n >> 1;
	d = c + 1;
	frec(c, d, a, b);
	rez1 = (c * c) % mod;
	rez2 = (c * d + c * d) % mod;
  }
  else
  {
	d = n >> 1;
	c = d - 1;
	frec(c, d, a, b);
	rez1 = (a * b + a * b) % mod;
	rez2 = (b * b) % mod;
  }
}

int main()
{
  freopen("ciuperci.in", "r", stdin);
  freopen("ciuperci.out", "w", stdout);
  int nrquery, i;
  long long n, a, b;
  scanf("%d", &nrquery);
  for(i = 1; i <= nrquery; ++ i)
  {
	scanf("%lld", &n);
	frec(n, n + 1, a, b);
	printf("%lld\n", a);
  }
  return 0;
}