#include "prison.h"
#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;
using std::begin;
using std::end;
using ll = long long;
constexpr int inf = (1 << 30) - 1;
constexpr ll infll = (1ll << 62) - 1;
vector<vector<int>> devise_strategy(int N) {
const int D = 8;
const int M = 22;
vector pow3(D, 1);
for (int i = 1; i < D; ++i) {
pow3[i] = pow3[i - 1] * 3;
}
const auto get = [&](int i, int d) {
return (i / pow3[d]) % 3;
};
vector S(M + 1, vector(N + 1, 0));
{
S[0][0] = 0;
for (int i = 1; i <= N; ++i) {
S[0][i] = (D - 1) * 3 - 1 + get(i, D - 1);
}
}
{
S[1][0] = 0;
for (int i = 1; i <= N; ++i) {
S[1][i] = (i % 3 == 0) ? -1 : -2;
}
}
for (int d = D - 1; d >= 1; --d) {
const int type = (D - d) & 1;
for (int r = 0; r <= 2; ++r) {
const int u = d * 3 - 1 + r;
S[u][0] = type;
for (int i = 1; i <= N; ++i) {
const int k = get(i, d);
if (r == k) {
const int k2 = get(i, d - 1);
if (d == 1) {
if (k2 == 1) {
S[u][i] = 1;
} else {
S[u][i] = ((k == 1) xor type) ? -1 : -2;
}
} else {
S[u][i] = (d - 1) * 3 - 1 + k2;
}
} else {
S[u][i] = ((r > k) xor type) ? -1 : -2;
}
}
}
}
return S;
}
