#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> devise_strategy(int N) {
vector<int> pow3(9, 1);
for (int i = 1; i < 9; ++i) pow3[i] = pow3[i - 1] * 3;
auto digit = [&](int v, int p) {
return (v / pow3[p]) % 3;
};
vector<vector<int>> s(21, vector<int>(N + 1, 0));
s[0][0] = 0;
for (int j = 1; j <= N; ++j) {
s[0][j] = 1 + digit(j - 1, 7);
}
for (int p = 7; p >= 0; --p) {
int bbase = 1 + (7 - p) * 2;
int abase = bbase + 3;
for (int d = 0; d < 3; ++d) {
int st = bbase + d;
s[st][0] = 1;
for (int j = 1; j <= N; ++j) {
int e = digit(j - 1, p);
if (e < d) s[st][j] = -2;
else if (e > d) s[st][j] = -1;
else if (p == 0) s[st][j] = -1;
else s[st][j] = abase;
}
}
if (p > 0) {
s[abase][0] = 0;
for (int j = 1; j <= N; ++j) {
s[abase][j] = abase + 1 + digit(j - 1, p - 1);
}
}
}
return s;
}
