#include "prison.h"
#include <bits/stdc++.h>
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define fe(x, y) for (auto& x : y)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define pw(x) (1LL << (x))
#define sz(x) (int)x.size()
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ve = vector <T>;
template <typename T>
bool umx (T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T>
bool umn (T& a, T b) { return a > b ? a = b, 1 : 0; }
using ll = long long;
using ld = long double;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
const int oo = 1e9;
const ll OO = 1e18;
const int N = 2e5 + 100;
const int M = 5e3 + 100;
const int mod = 1e9 + 7;
const bool TEST = 1;
int nedobpw(int a, int n) {
int x = 1;
for (int i = 0; i < n; i++) {
x *= a;
}
return x;
}
vector <vector<int>> devise_strategy(int N) {
// freopen("log.txt", "w", stdout);
ve <ve <int>> Z(25);
// cout << "N: " << N << "\n";
for (int i = 0; i <= 24; i++) {
Z[i].resize(N + 1);
int X = i / 3;
int Y = i % 3;
if (!X && !Y) Z[i][0] = 0;
else if (X & 1) Z[i][0] = 0;
else Z[i][0] = 1;
for (int j = 1; j <= N; j++) {
int cnt = 0;
if (X || Y) {
cnt = X;
} else {
Z[i][j] = (j / nedobpw(3, 7)) % 3 + 3 * 7;
continue;
}
int K = j;
K /= nedobpw(3, cnt);
if (K % 3 > Y) {
if (X&1) Z[i][j] = -2;
else Z[i][j] = -1;
} else if (K % 3 < Y) {
if (X&1) Z[i][j] = -1;
else Z[i][j] = -2;
} else {
if (cnt == 0) {
Z[i][j] = -1;
} else {
if(cnt == 1 && j % 3 == 0) {
Z[i][j] = -1 - (X&1);
} else {
Z[i][j] = (j / nedobpw(3, cnt - 1)) % 3 + 3 * (cnt - 1);
}
}
}
}
}
return Z;
}
