#include "hack.h"
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1tst"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
int rand(int l,int r)
{
return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf = 1e18;
const int mod2 = 1e9+7;
const double lim=9;
ll n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2,
r2, center;
ll i, s10, s12, k1, k2, k3, s11, w, l, r, dem5, dem6, dem7, dem9,q;
ll el = 19;
int B=31622;
bool ask(vector<ll>vl,vector<ll> vr)
{
for(auto x:vr)vl.pb(x);
return collisions(vl)>0;
}
int work(vector<ll> va,vector<ll> vb)
{
if(va.size()==1&&vb.size()==1)
{
return vb[0]-va[0];
}
if(va.size()>vb.size())
{
vector<ll> vl,vr;
int mid=va.size()>>1;
for(int i=0; i<va.size(); i++)
if(i<mid)vl.pb(va[i]);
else vr.pb(va[i]);
if(ask(vr,vb))return work(vr,vb);
return work(vl,vb);
}
else
{
int mid=vb.size()>>1;
vector<ll> vl,vr;
for(int i=0; i<vb.size(); i++)
if(i<mid)vl.pb(vb[i]);
else vr.pb(vb[i]);
if(ask(va,vl))return work(va,vl);
return work(va,vr);
}
}
int hack()
{
vector<ll> va,vb;
int x=B;
for(int i=1; i<=B; i++)
va.pb(i);
for(int j=B*2; j; j+=B)
{
vb.pb(j);
if(j>1e9)break;
}
x=work(va,vb);
vector<int> vcl;
for(int i=1; i<=sqrt(x); i++)
if(x%i==0&&!B%i==0 )
{
vcl.pb(i);
if(x/i!=i)vcl.pb(x/i);
}
sort(vcl.begin(),vcl.end());
for(auto t:vcl)
if(collisions({1,t+1})>0)return t;
assert(0);
}
