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

#define restRez 666013
#define ll long long

#define pb push_back

using namespace std;
using namespace tr1;

unordered_map <ll, ll> sol;

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

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

		vector <ll> vctCalc;
		vctCalc.pb(n);
		for (int i = 0; i < vctCalc.size(); i++)
		{
			ll x = vctCalc[i];

			x--;
			if (x - x / 2 && x - x / 2 < vctCalc[vctCalc.size() - 1])
				vctCalc.pb(x - x / 2);
			if (x / 2 && x / 2 < vctCalc[vctCalc.size() - 1])
				vctCalc.pb(x / 2);
		}

		reverse(vctCalc.begin(), vctCalc.end());

		sol[1] = 1;
		sol[0] = 1;
		for (int i = 0; i < vctCalc.size(); i++)
		{
			ll x = vctCalc[i];
			
			if (sol[x])
				continue;

			x--;

			ll s1 = sol[x / 2], s2 = sol[x - (x / 2)];

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

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

	return 0;
}