#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second
class Solver{
private:
ll n;
vvi known;
void typeZeroQuery (ll x){
ll res = use_machine(vi{0,x});
known[res].push_back(x);
}
void typeOneQuery(ll x1, ll x2){
ll curType = 0;
if (2 > known[0].size()) curType = 1;
vi v = {known[curType][0],x1,known[curType][1],x2};
ll res = use_machine(v);
if (res & 2){
known[1-curType].push_back(x1);
}else{
known[curType].push_back(x1);
}
if (res & 1){
known[1-curType].push_back(x2);
}else{
known[curType].push_back(x2);
}
}
public:
Solver(ll n): n(n){
}
ll solve(){
known.assign(2,vi());
known[0].push_back(0);
for (ll i = 1; 3 > i && n > i; i++){
typeZeroQuery(i);
}
for (ll i = 3; n > i+1; i+=2){
typeOneQuery(i,i+1);
}
if (n%2 == 0) typeZeroQuery(n-1);
return known[0].size();
}
};
int count_mushrooms(int n) {
Solver mySolver(n);
return mySolver.solve();
}
