#include <bits/stdc++.h>
#include "richest.h"
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9;
const ll J=1e18;
int md[1000007];
int b[8]={2,2,2,2,3,6,19,183};
int d[1007][1007];
vector<int> aask(vector<int> a,vector<int> b) {
	vector<int> ret;
	assert(a.size()==b.size());
	for (int i=0;i<a.size();i++) ret.pb(md[a[i]]<md[b[i]]?1:2);
	return ret;
}
vector<int> get(vector<int> now,int na,int xa,int nb,int xb) {
	assert(now.size()<na*xa+nb*xb);
	vector<int> a,b,c;
	for (int i=0;i<na;i++) {
		for (int j=0;j<xa;j++) for (int k=j+1;k<xa;k++)
			a.pb(now[i*xa+j]),b.pb(now[i*xa+k]);
	}
	for (int i=0;i<nb;i++) {
		for (int j=0;j<xb;j++) for (int k=j+1;k<xb;k++)
			a.pb(now[na*xa+i*xb+j]),b.pb(now[na*xa+i*xb+k]);
	}
	c=ask(a,b);
	vector<int> ret;
	int tmp=0;
	for (int i=0;i<na;i++) {
		for (int j=0;j<xa;j++) for (int k=j+1;k<xa;k++)
			d[j][k]=c[tmp++],d[k][j]=3-d[j][k];
		for (int j=0;j<xa;j++) {
			int flg=1;
			for (int k=0;k<xa;k++) if (j!=k&&d[j][k]!=2) { flg=0; break; }
			if (flg) { ret.pb(now[i*xa+j]); break; }
		}
	}
	for (int i=0;i<nb;i++) {
		for (int j=0;j<xb;j++) for (int k=j+1;k<xb;k++)
			d[j][k]=c[tmp++],d[k][j]=3-d[j][k];
		for (int j=0;j<xb;j++) {
			int flg=1;
			for (int k=0;k<xb;k++) if (j!=k&&d[j][k]!=2) { flg=0; break; }
			if (flg) { ret.pb(now[na*xa+i*xb+j]); break; }
		}
	}
	return ret;
}
int richest(int n,int t,int s) {
	vector<int> now;
	for (int i=0;i<n;i++) now.pb(i);
	if (n==1000) now=get(now,1,1000,0,0);
	else {
		now=get(now,500000,2,0,0);
		now=get(now,250000,2,0,0);
		now=get(now,125000,2,0,0);
		now=get(now,62500,2,0,0);
		now=get(now,20832,3,1,4);
		now=get(now,3471,6,1,7);
		now=get(now,178,19,5,18);
		now=get(now,1,183,0,0);
	}
	return now[0];
}
mt19937 dnr(time(0));
void mian() {
	ll n=1e6;
	iota(md,md+n,0);
	shuffle(md,md+n,dnr);
//	for (int i=0;i<n;i++) printf("%d ",md[i]); printf("\n");
	int res=richest(n,8,1099944);
	printf("%d  %d\n",res,(int)(max_element(md,md+n)-md));
	if (max_element(md,md+n)-md!=res) cout<<"NOOOO",exit(0);
}
bool ORY; int maain() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	while (1)
	int t; for (scanf("%d",&t);t--;)
	mian();
	cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB";
	return 0;
}