#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef pair<pii, int> piipi;
typedef pair<int, pii> pipii;
typedef pair<pii, pii> piipii;
typedef pair<ll, pii> plpii;
typedef pair<db, db> pdd;
typedef pair<ld, ld> pldd;
typedef vector<int> vi;
typedef vector<pii> vii;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FOR2(i, a, b) for(int i=(a);i<=(b);++i)
#define ROF(i, a, b) for(int i=(b)-1;i>=(a);--i)
#define ROF2(i, a, b) for(int i=(b);i>=(a);--i)
#define GO(i, x) for(auto &i : x)
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define eb emplace_back
#define pf push_front
#define pb push_back
#define lb lower_bound
#define up upper_bound
template<typename T> inline bool min2(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool max2(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
// const int mod = 998244353;
const int P1 = 999983, P2 = 999979;
const ld PI = acos((ld)-1);
const int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const ll INF = 1e18;
const int N = 1e6;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int sq = 161;
int use_machine(vector<int> x);
int count_mushrooms(int n){
int ansA = 0, ansB = 0;
vector<int> A, B;
A.eb(0);
int k = 1;
if(n <= sq+10){
while(sz(A) + sz(B) < n){
vector<int> x;
x.eb(0);
x.eb(k);
int res = use_machine(x);
if(res == 0) A.eb(k);
else B.eb(k);
k++;
}
ansA = sz(A);
ansB = sz(B);
}
else{
while(sz(A) < sq && sz(B) < sq){
vector<int> x;
x.eb(0);
x.eb(k);
int res = use_machine(x);
if(res == 0) A.eb(k);
else B.eb(k);
k++;
}
// while((sz(A) < 3 && sz(B) < 2) || (sz(B) < 2 && sz(A) < 3)){
// vector<int> x;
// bool sw = 0;
// if(sz(A) < sz(B)){
// sw = 1;
// swap(A, B);
// }
// x.eb(k);
// x.eb(A[0]);
// x.eb(k+1);
// x.eb(A[1]);
// int res = use_machine(x);
// if(res%2 == 0) A.eb(k);
// else B.eb(k);
// if(res/2 == 0) A.eb(k+1);
// else B.eb(k+1);
// k+=2;
// if(sw) swap(A, B);
// }
// while(sz(A) < sq && sz(B) < sq){
// vector<int> x;
// bool sw = 0;
// if(sz(A) < sz(B)){
// sw = 1;
// swap(A, B);
// }
// x.eb(k);
// x.eb(A[0]);
// x.eb(k+1);
// x.eb(A[1]);
// x.eb(k+2);
// x.eb(A[2]);
// int res = use_machine(x);
// if(res%2 == 0) A.eb(k);
// else B.eb(k);
// if(res/2 == 0) A.eb(k+1), A.eb(k+2), k += 3;
// else if(res/2 == 2) B.eb(k+1), B.eb(k+1), k += 3;
// else{
// x.clear();
// x.eb(B[0]);
// x.eb(k+1);
// x.eb(B[1]);
// x.eb(A[0]);
// x.eb(k+2);
// x.eb(A[1]);
// x.eb(k+3);
// x.eb(A[2]);
// x.eb(k+4);
// if(res%2 == 0) A.eb(k+4);
// else B.eb(k+4);
// if(res >= 4){
// A.eb(k+1);
// B.eb(k+2);
// if(res < 6) A.eb(k+3);
// else B.eb(k+3);
// }
// else{
// B.eb(k+1);
// A.eb(k+2);
// if(res < 2) A.eb(k+3);
// else B.eb(k+3);
// }
// k += 5;
// }
// if(sw) swap(A, B);
// }
ansA = sz(A);
ansB = sz(B);
while(ansA + ansB < n){
vector<int> x;
bool sw = 0;
if(sz(A) < sz(B)){
sw = 1;
swap(A, B);
swap(ansA, ansB);
}
int le = min(sz(A), n-k);
for(int i=0;i<le;i++){
x.eb(k+i);
x.eb(A[i]);
}
int res = use_machine(x);
if(res%2 == 0) A.eb(k), ansA++;
else B.eb(k), ansB++;
ansA += (le-1) - res/2;
ansB += res/2;
k += le;
if(sw){
swap(A, B);
swap(ansA, ansB);
}
}
}
return ansA;
}
