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

#define restRez 666013
#define ll long long

#define pb push_back

using namespace std;

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

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

		set <ll> setNr;
		setNr.insert(-n);

		vector <ll> vctCalc;
		for (; !setNr.empty(); setNr.erase(setNr.begin()))
		{
			ll x = -(*setNr.begin());

			vctCalc.pb(x);

			x--;
			if (x / 2)
				setNr.insert(-(x / 2));
			if (x - x / 2)
				setNr.insert(-(x - x / 2));
		}

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

		map <ll, ll> sol;
		/*sol[1] = 1;
		sol[0] = 1;
		for (int i = 0; i < vctCalc.size(); i++)
		{
			ll x = vctCalc[i];
			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;
}