#include <bits/stdc++.h>
using namespace std;
int val[10];
int a[5][5];
void cal();
void rotate(int cur);
void rerotate(int cur);
int chin(int step, int point, int end, int rot);
int main() {
    int T;
    cin >> T;
    while (T--) {
        int k;
        cin >> k;
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                cin >> a[i][j];
            }
        }
        rerotate(1);
        cout << chin(0, 0, 2 * k, 1);
    }
    return 0;
}

void cal() {
    val[0] = a[1][1] + a[1][2] + a[2][1] + a[2][2];
    val[1] = a[1][3] + a[1][4] + a[2][3] + a[2][4];
    val[2] = a[3][1] + a[3][2] + a[4][1] + a[4][2];
    val[3] = a[3][3] + a[3][4] + a[4][3] + a[4][4];
    val[4] = a[2][2] + a[3][3] + a[2][3] + a[3][2];
    val[5] = a[1][2] + a[1][3] + a[2][2] + a[2][3];
    val[6] = a[3][2] + a[3][3] + a[4][2] + a[4][3];
    val[7] = a[2][1] + a[2][2] + a[3][1] + a[3][2];
    val[8] = a[2][3] + a[2][4] + a[3][3] + a[3][4];
}
void rotate(int cur) {
    int temp[2][2];
    int x, y;
    if (cur == 0) {
        x = 1;
        y = 1;
    }
    if (cur == 1) {
        x = 1;
        y = 3;
    }
    if (cur == 2) {
        x = 3;
        y = 1;
    }
    if (cur == 3) {
        x = 3;
        y = 3;
    }
    if (cur == 4) {
        x = 2;
        y = 2;
    }
    if (cur == 5) {
        x = 1;
        y = 2;
    }
    if (cur == 6) {
        x = 3;
        y = 2;
    }
    if (cur == 7) {
        x = 2;
        y = 1;
    }
    if (cur == 8) {
        x = 2;
        y = 3;
    }
    temp[0][0] = a[x][y + 1];
    temp[1][0] = a[x][y];
    temp[0][1] = a[x + 1][y + 1];
    temp[1][1] = a[x + 1][y];
    a[x][y] = temp[0][0];
    a[x][y + 1] = temp[0][1];
    a[x + 1][y] = temp[1][0];
    a[x + 1][y + 1] = temp[1][1];
    cal();
}
void rerotate(int cur) {
    int temp[2][2];
    int x, y;
    if (cur == 0) {
        x = 1;
        y = 1;
    }
    if (cur == 1) {
        x = 1;
        y = 3;
    }
    if (cur == 2) {
        x = 3;
        y = 1;
    }
    if (cur == 3) {
        x = 3;
        y = 3;
    }
    if (cur == 4) {
        x = 2;
        y = 2;
    }
    if (cur == 5) {
        x = 1;
        y = 2;
    }
    if (cur == 6) {
        x = 3;
        y = 2;
    }
    if (cur == 7) {
        x = 2;
        y = 1;
    }
    if (cur == 8) {
        x = 2;
        y = 3;
    }
    temp[0][0] = a[x + 1][y];
    temp[1][0] = a[x + 1][y + 1];
    temp[0][1] = a[x][y];
    temp[1][1] = a[x][y + 1];
    a[x][y] = temp[0][0];
    a[x][y + 1] = temp[0][1];
    a[x + 1][y] = temp[1][0];
    a[x + 1][y + 1] = temp[1][1];
    cal();
}
int chin(int step, int point, int end, int rot) {
    rotate(rot);
    if (step == end) {
        return point;
    }
    if (step % 2 == 0) {
        int maxAns = 0;
        for (int i = 0; i < 9; i++) {
            int v = chin(step + 1, point + val[i], end, i);
            if (v > maxAns)
                maxAns = v;
            rerotate(i);
        }
        return maxAns;
    } else if (step % 2 == 1) {
        int minAns = INT_MAX;
        for (int i = 0; i < 9; i++) {
            int v = chin(step + 1, point + val[i], end, i);
            if (v < minAns)
                minAns = v;
            rerotate(i);
        }
        return minAns;
    }
    return 0;
}