#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> a = {1, 6, 20, 62, 188, 566, 1698, 5096};
int mv[22];
int v[22];
int get(int x, int b){
for (int i = 1; i < b; i++){
if (x == 0) return -3;
if (x == a[i - 1] - 1) return -3;
x--;
x %= a[i];
}
if (x == 0) return -1;
if (x == a[b - 1] - 1) return -2;
x--;
return x / a[b];
}
vector<vector<int>> devise_strategy(int n) {
reverse(a.begin(), a.end());
vector<vector<int>> ans(21, vector<int>(n + 1, 0));
mv[0] = mv[1] = mv[2] = mv[3] = 1;
mv[4] = mv[5] = mv[6] = 2;
mv[7] = mv[8] = mv[9] = 3;
mv[10] = mv[11] = mv[12] = 4;
mv[13] = mv[14] = mv[15] = 5;
mv[16] = mv[17] = mv[18] = 6;
mv[19] = 7;
mv[20] = 7;
v[1] = v[4] = v[7] = v[10] = v[13] = v[16] = 0;
v[2] = v[5] = v[8] = v[11] = v[14] = v[17] = 1;
v[3] = v[6] = v[9] = v[12] = v[15] = v[18] = 2;
for (int i = 0; i <= 20; i++){
if (i == 0){
ans[i][0] = 0;
for (int j = 1; j <= n; j++){
int xx = get(j, mv[i]);
if (xx == -1) ans[i][j] = -1;
else if (xx == -2) ans[i][j] = -2;
else if (xx == -3) ans[i][j] = 0;
else ans[i][j] = 1 + xx;
}
} else if (i == 19){
ans[i][0] = 1;
for (int j = 1; j <= n; j++){
int bb = get(j, mv[i]);
if (bb == -1 || bb == 0) ans[i][j] = -2;
else if (bb == -2 || bb == 3) ans[i][j] = -1;
else ans[i][j] = 20;
}
} else if (i == 20){
ans[i][0] = 0;
for (int j = 1; j <= n; j++){
int aa = get(j, mv[i]);
if (aa == -1 || aa == 0 || aa == 1) ans[i][j] = -1;
else ans[i][j] = -2;
}
} else if (i >= 16){
ans[i][0] = 0;
for (int j = 1; j <= n; j++){
int aa = get(j, mv[i]);
int bb = v[i];
if (aa == -1) ans[i][j] = -1;
else if (aa == -2) ans[i][j] = -2;
else if (aa == -3) ans[i][j] = 0;
else if (aa < bb) ans[i][j] = -1;
else if (bb < aa) ans[i][j] = -2;
else {
aa = get(j, mv[i] + 1);
if (aa == -1) ans[i][j] = -1;
else if (aa == -2) ans[i][j] = -2;
else if (aa == -3) ans[i][j] = 0;
else ans[i][j] = 19;
}
}
} else if (i % 6 == 1 || i % 6 == 2 || i % 6 == 3) {
ans[i][0] = 1;
for (int j = 1; j <= n; j++){
int aa = v[i];
int bb = get(j, mv[i]);
if (bb == -1) ans[i][j] = -2;
else if (bb == -2) ans[i][j] = -1;
else if (bb == -3) ans[i][j] = 0;
else if (aa < bb) ans[i][j] = -1;
else if (bb < aa) ans[i][j] = -2;
else {
bb = get(j, mv[i] + 1);
if (bb == -1) ans[i][j] = -2;
else if (bb == -2) ans[i][j] = -1;
else if (bb == -3) ans[i][j] = 0;
else ans[i][j] = i - v[i] + 3 + bb;
}
}
} else {
ans[i][0] = 0;
for (int j = 1; j <= n; j++){
int aa = get(j, mv[i]);
int bb = v[i];
if (aa == -1) ans[i][j] = -1;
else if (aa == -2) ans[i][j] = -2;
else if (aa == -3) ans[i][j] = 0;
else if (aa < bb) ans[i][j] = -1;
else if (bb < aa) ans[i][j] = -2;
else {
aa = get(j, mv[i] + 1);
if (aa == -1) ans[i][j] = -1;
else if (aa == -2) ans[i][j] = -2;
else if (aa == -3) ans[i][j] = 0;
else ans[i][j] = i - v[i] + 3 + aa;
}
}
}
}
return ans;
}
// int main(){
// int n; cin >> n;
// auto ans = devise_strategy(n);
// // for (auto x : ans){
// // for (auto y : x){
// // cout << y << " ";
// // }
// // cout << "\n";
// // }
// return 0;
// }
