#pragma GCC optimize("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include "mushrooms.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define e1 first
#define e2 second
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define float long double
#define size(x) (int)x.size()
#define satori int testCases; cin>>testCases; while(testCases--)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(r) begin(r),end(r)
#define time chrono::high_resolution_clock().now().time_since_epoch().count()
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
float pi=3.14159265358979323846;
int prep=77;
int count_mushrooms(int n)
{
vector<int> unknown,red={0},blue,qvec;
for(int i=1;i<n;i++)
unknown.eb(i);
mt19937 rng(time);
uniform_int_distribution<int> rng2(0,1);
shuffle(all(unknown),rng);
int res=1;
while(size(unknown)>1&&prep>0)
{
prep--;
qvec.clear();
if(max(size(red),size(blue))==1)
{
qvec.eb(red[0]);
qvec.eb(unknown.back()),unknown.pop_back();
int ans=use_machine(qvec);
if(ans==1)
blue.eb(qvec.back());
else
red.eb(qvec.back()),res++;
}
else
if(min(size(red),size(blue))<2)
{
if(size(red)>1)
{
qvec.eb(red[0]);
qvec.eb(unknown.back()),unknown.pop_back();
qvec.eb(red[1]);
qvec.eb(unknown.back()),unknown.pop_back();
int ans=use_machine(qvec);
if(ans==0)
res+=2,red.eb(qvec[1]),red.eb(qvec[3]);
else
if(ans==1)
res+=1,red.eb(qvec[1]),blue.eb(qvec[3]);
else
if(ans==2)
res+=1,red.eb(qvec[3]),blue.eb(qvec[1]);
else
if(ans==3)
blue.eb(qvec[1]),blue.eb(qvec[3]);
}
else
{
qvec.eb(blue[0]);
qvec.eb(unknown.back()),unknown.pop_back();
qvec.eb(blue[1]);
qvec.eb(unknown.back()),unknown.pop_back();
int ans=use_machine(qvec);
if(ans==0)
blue.eb(qvec[1]),blue.eb(qvec[3]);
else
if(ans==1)
res+=1,blue.eb(qvec[1]),red.eb(qvec[3]);
else
if(ans==2)
res+=1,blue.eb(qvec[3]),red.eb(qvec[1]);
else
if(ans==3)
res+=2,red.eb(qvec[1]),red.eb(qvec[3]);
}
}
else
{
if(rng2(rng)&1)
{
qvec.eb(red[0]);
qvec.eb(unknown.back()),unknown.pop_back();
qvec.eb(red[1]);
qvec.eb(unknown.back()),unknown.pop_back();
int ans=use_machine(qvec);
if(ans==0)
res+=2,red.eb(qvec[1]),red.eb(qvec[3]);
else
if(ans==1)
res+=1,red.eb(qvec[1]),blue.eb(qvec[3]);
else
if(ans==2)
res+=1,red.eb(qvec[3]),blue.eb(qvec[1]);
else
if(ans==3)
blue.eb(qvec[1]),blue.eb(qvec[3]);
}
else
{
qvec.eb(blue[0]);
qvec.eb(unknown.back()),unknown.pop_back();
qvec.eb(blue[1]);
qvec.eb(unknown.back()),unknown.pop_back();
int ans=use_machine(qvec);
if(ans==0)
blue.eb(qvec[1]),blue.eb(qvec[3]);
else
if(ans==1)
res+=1,blue.eb(qvec[1]),red.eb(qvec[3]);
else
if(ans==2)
res+=1,blue.eb(qvec[3]),red.eb(qvec[1]);
else
if(ans==3)
res+=2,red.eb(qvec[1]),red.eb(qvec[3]);
}
}
}
while(size(unknown))
{
qvec.clear();
if(size(red)>size(blue))
{
int p=0;
while(p<size(red)&&size(unknown)>0)
qvec.eb(red[p++]),qvec.eb(unknown.back()),unknown.pop_back();
int ans=use_machine(qvec);
if(ans&1)
blue.eb(qvec.back()),ans++;
else
red.eb(qvec.back());
ans/=2;
res+=p-ans;
}
else
{
int p=0;
while(p<size(blue)&&size(unknown)>0)
qvec.eb(blue[p++]),qvec.eb(unknown.back()),unknown.pop_back();
int ans=use_machine(qvec);
if(ans&1)
red.eb(qvec.back()),ans++;
else
blue.eb(qvec.back());
ans/=2;
res+=ans;
}
}
return res;
}
