#include <bits/extc++.h>
using namespace std;
int use_machine(vector<int> x);
int f(int n) {
int b = 0;
for (int i = 1; i + 1 < n; i += 2) b += use_machine({i, 0, i + 1});
if ((n & 1) == 0) b += use_machine({0, n - 1});
return n - b;
}
// sqrt(20000) = 141.xx
vector<int> a[2] = {{0}, {}};
int idx = 1, k = 79;
// rule: https://oj.uz/submission/303279 ....
map<vector<int>, string> prec1 = {{{}, "A0B0C0DE"}, {{1}, "CED"}, {{2}, "DBE0A"}, {{3}, "CB0E0DA1"},
{{4}, "D0A0E0CB1"}, {{5}, "DBCE1"}, {{6}, "CED"}};
map<vector<int>, string> prec2 = {{{}, "ABCDE0"}, {{1}, "B0"}, {{1, 1}, "EADC"}, {{2}, "CB0D"},
{{2, 1}, "EADB"}, {{2, 2}, "DAE0CB"}, {{3}, "CB0D"}, {{3, 1}, "EDB0"},
{{3, 2}, "AED"}, {{3, 3}, "ED"}, {{4}, "B0"}, {{4, 1}, "0EACD"}};
int chk(string& s, int state) {
int ret = 0;
for (char& c: s) {
if ('A' <= c && c <= 'Z') c = (char) ('0' + ((state) >> (c - 'A') & 1));
}
for (int i = 1; i < s.size(); i++) ret += s[i - 1] != s[i];
}
int count_mushrooms(int n) {
if (n <= 450) return f(n);
int ret = 0;
while (idx < n) {
int t = a[0].size() < a[1].size();
if (n - idx < 5 || a[t].size() >= k) {
int t = (a[0].size() < a[1].size());
vector<int> query, &c = a[t];
int qcnt = 0;
for (int i = 0; i < c.size() && idx < n; i++) query.push_back(c[i]), query.push_back(idx++), qcnt++;
// for (auto qq: q) cout << qq << ' ';
// cout << endl;
int cnt = use_machine(query);
int p = cnt / 2 + (cnt & 1);
if (cnt & 1) a[t ^ 1].push_back(idx - 1), ret += p;
else a[t].push_back(idx - 1), ret += qcnt - p;
}
else { // 다 쳐넣음
map<vector<int>, string>& rule = a[t].size() >= 3 && a[t ^ 1].size() >= 1 ? prec1 : prec2;
vector<int> record, cnt(2, 0), valid(32, 1);
for (int i = 0; i < 5; i++) record.push_back(i + idx);
while (rule.count(record)) {
vector<int> query;
for (char c: record) {
if (c == '0' || c == '1') query.push_back(a[(c - '0') ^ 1][cnt[(c - '0') ^ 1]]++);
else query.push_back(idx + (c - 'A'));
}
int q = use_machine(query);
record.push_back(q);
for (int state = 0; state < 32; state++) {
if (chk(rule[record], state) != q) valid[state] = 0;
}
}
for (int state = 0; state < 32; state++) {
if (valid[state]) {
for (int i = 0; i < 5; i++) {
a[(state >> i & 1) ^ t].push_back((idx++) + i);
ret += ((state >> i & 1) ^ t) == 0;
}
break;
}
}
}
}
return ret;
}
