#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
//#define int long long
#define ll int
#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".ans","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 = 998244353;
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, root,q;
ll el = 19;
int a[10]= {1666,555,185,61,20,6,2};
int base[10]= {5000,1665,554,184,60,19,5,1};
vector<vector<int>> devise_strategy(int N)
{
vector<vector<int>>f;
f.assign(21, vector<int>(N + 1));
for(int i=0; i<=20; i++)
{
int y=0;
if(i==0)f[i][0]=0;
else f[i][0]=((i-1)/3+1)%2,y=(i-1)/3+1;
vector<int> vc;
for(int j=1; j<=N; j++)
{
vc.pb(j);
int x=j;
int lx=j;
for(int z=0; z<y; z++)lx=x,x=x%a[z];
///-1 0 1 2 3 4 5
if(i!=0&&i-(y-1)*3!=lx/a[y-1])
{
lx=(lx-1)/a[y-1]+1;
if(i-(y-1)*3<lx)
{
if(f[i][0]==0)f[i][j]=-1;
else f[i][0]=-2;
}
else
{
if(f[i][0]==0)f[i][j]=-2;
else f[i][0]=-1;
}
}
else if(x==0)
{
if(f[i][0]==0)f[i][j]=-1;
else f[i][0]=-2;
}
else if(x==base[y])
{
if(f[i][0]==0)f[i][j]=-2;
else f[i][0]=-1;
}
else
{
int hh=(x-1)/a[y]+1+y*3;
if(i==19||i==20)
{
if(hh==0)
{
if(f[i][0]==0)f[i][j]=-1;
else f[i][0]=-2;
}
else
{
if(f[i][0]==0)f[i][j]=-2;
else f[i][0]=-1;
}
}
else{
f[i][j]=hh;
}
}
}
}
return f;
}
