#include <algorithm>
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <vector>
#include <set>

#define restRez 666013
#define ll long long

#define pb push_back

using namespace std;

ll vctCalc[256], sol[256];

int main()
{
	ifstream cin("ciuperci.in");
	ofstream cout("ciuperci.out");

	int testCases;
	for (cin >> testCases; testCases; testCases--)
	{
		ll n;
		cin >> n;

		vctCalc[0] = 0;
		vctCalc[++vctCalc[0]] = n;
		for (int i = 1; i <= vctCalc[0]; i++)
		{
			ll x = vctCalc[i];

			x--;
			if (x - x / 2 && x - x / 2 < vctCalc[vctCalc[0]])
				vctCalc[++vctCalc[0]] = x - x / 2;
			if (x / 2 && x / 2 < vctCalc[vctCalc[0]])
				vctCalc[++vctCalc[0]] = x / 2;
		}

		vctCalc[++vctCalc[0]] = 0;
		reverse(vctCalc + 1, vctCalc + 1 + vctCalc[0]);

		int pr = 1;
		sol[1] = sol[2] = 1;
		for (int i = 3; i <= vctCalc[0]; i++)
		{
			ll x = vctCalc[i];
			x--;

			for (; vctCalc[pr] < x / 2; pr++);

			ll s1 = sol[pr], s2 = sol[pr];
			if (x & 1)
				s2 = sol[pr + 1];

			if (x & 1)
				sol[i] = 2 * s1 * s2 % restRez;
			else sol[i] = s1 * s2 % restRez;
		}

		cout << sol[vctCalc[0]] << '\n';
	}

	return 0;
}