#include "mushrooms.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "stub.cpp"
#endif
using ll = int;
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(), a.end()
int count_mushrooms(int n) {
vi A, B;
A.pb(0);
int now = 1;
int ans = 1;
while(now < n){
if(A.size() > B.size()){
vi query;
int maxi = 0;
rep(i,0,A.size()){
if(now == n) break;
query.pb(now);
query.pb(A[i]);
now++;
ans++;
maxi++;
}
int res = use_machine(query);
if(res%2) ans--;
ans -= res/2;
if(res%2){
B.pb(query[0]);
}
else{
A.pb(query[0]);
}
if(res/2 == 0){
rep(i,1,query.size()/2) A.pb(query[i*2]);
}
if(res/2 == maxi-1){
rep(i,1,query.size()/2) B.pb(query[i*2]);
}
}
else{
vi query;
int maxi = 0;
rep(i,0,B.size()){
if(now == n) break;
query.pb(now);
query.pb(B[i]);
now++;
maxi++;
}
int res = use_machine(query);
if(res%2) ans++;
ans += res/2;
if(res%2){
A.pb(query[0]);
}
else{
B.pb(query[0]);
}
if(res/2 == 0){
rep(i,1,query.size()/2) B.pb(query[i*2]);
}
if(res/2 == maxi-1){
rep(i,1,query.size()/2) A.pb(query[i*2]);
}
}
}
return ans;
}
