#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i) 
#define R(i, j, k) for(int i = (j); i >= (k); --i) 
#define ll long long 
#define vi vector < int > 
#define sz(a) ((int) (a).size())
#define me(a, x) memset(a, x, sizeof(a))
using namespace std;
const int N = 1e5 + 7;
int a[N], col[N][20], cc[N][20], P[20];
int n, d;
void solve(int l, int r, int t, int v) {
	if(l > r) return ;
	L(i, l, r) col[i][t] = cc[i][t] = v;
	d = max(d, t), P[t] = max(P[t], v + 1);
	L(a, t, 12) cc[l][a] = -1, cc[r][a] = -2;
	++l, --r;
	if(l > r) return ;
	int len = r - l + 1;
	int a = (len + 2) / 3;
	int b = (len + 1) / 3;
	int c = len / 3;
	if(len == 2) a = 2, b = 0;
	if(len == 3) a = 2, b = 1, c = 0;
	if(len == 4) a = b = 2, c = 0;
	a += l, b += a, c += b;
	solve(l, a - 1, t + 1, 0);
	solve(a, b - 1, t + 1, 1);
	solve(b, c - 1, t + 1, 2);
}

void init() {
	me(col, -1), me(cc, -1);
	solve(1, n, 0, 0);
}

vector < vi > devise_strategy(int xn) {
	n = xn;
	int op = 0;
	vector < vi > T;
	init();
	P[0] = 1;
	int lim = 0;
//	L(i, 0, d) cout << P[i] << ' ';
//	cout << '\n';
	L(i, 0, d) {
		vi f(xn + 1);
		L(t, 0, P[i] - 1) {
			f[0] = op;
			L(o, 1, xn) {
				int qwq = cc[o][i];
				if(col[o][i] >= 0 && col[o][i] != t) {
					if(col[o][i] < t) {
						// op lose. 
						f[o] = op == 0 ? -1 : -2;
					} else if(col[o][i] > t) {
						// op win. 
						f[o] = op == 0 ? -2 : -1;
					}
					continue;
				}
				if(qwq == -1) {
					f[o] = op == 0 ? -1 : -2;
					continue ;
				} 
				if(qwq == -2) {
					f[o] = op == 0 ? -2 : -1;
					continue ;
				} 
				f[o] = lim + col[o][i + 1] + 1;
			}
			T.emplace_back(f);
		}
		op ^= 1;
		lim += P[i + 1];
	} 
	return T;
}

//int Get(int x) {
//	x -= 2;
//	if(x <= 0) return 0;
//	if(x <= 4) return 2;
//	return Get((x + 2) / 3) + 3;
//}

//int main() {
////	cout << Get(5000) << '\n';
//	ios :: sync_with_stdio(false);
//	cin.tie(0); cout.tie(0);
//	cout << sz(devise_strategy(5000)) << '\n';
////	auto x = devise_strategy();
////	for(auto u : x) {
////		for(auto w : u) cout << w << ' ';
////		cout << '\n';
////	}
//	return 0;
//}