#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> devise_strategy(int N) {
const int D = 8;
auto digit = [&](int v, int pos) {
int x = v - 1;
int p = 1;
for (int i = 0; i < D - 1 - pos; ++i) p *= 3;
return (x / p) % 3;
};
auto id = [&](int level, int d) {
if (level == D - 1) return 22;
return 1 + level * 3 + d;
};
vector<vector<int>> s(23, vector<int>(N + 1, 0));
s[0][0] = 0;
for (int j = 1; j <= N; ++j) {
s[0][j] = id(0, digit(j, 0));
}
for (int level = 0; level < D - 1; ++level) {
for (int d = 0; d < 3; ++d) {
int st = id(level, d);
s[st][0] = (level % 2 == 0 ? 1 : 0);
for (int j = 1; j <= N; ++j) {
int q = digit(j, level);
if (q < d) {
s[st][j] = (level % 2 == 0 ? -2 : -1);
} else if (q > d) {
s[st][j] = (level % 2 == 0 ? -1 : -2);
} else {
int nd = digit(j, level + 1);
if (level + 1 == D - 1) {
if (nd == 0) {
s[st][j] = (level % 2 == 0 ? -2 : -1);
} else if (nd == 2) {
s[st][j] = (level % 2 == 0 ? -1 : -2);
} else {
s[st][j] = id(level + 1, 1);
}
} else {
s[st][j] = id(level + 1, nd);
}
}
}
}
}
s[22][0] = 0;
for (int j = 1; j <= N; ++j) {
int q = digit(j, D - 1);
if (q == 0) s[22][j] = -1;
else if (q == 2) s[22][j] = -2;
else s[22][j] = -1;
}
return s;
}
