choosenum

/*
 Author: 曹北健(37509)
 Result: AC Submission_id: 4329393
 Created at: Sat Apr 16 2022 19:44:39 GMT+0800 (China Standard Time)
 Problem: 5581  Time: 7 Memory: 1732
*/

#include <stdio.h>
int map[16][16] = { 0 }, m;
int ans;
void dfs(int k, int v, int cursum){
    int i;
    if(k >= m){
        if(ans > cursum){
            ans = cursum;
        }
    }
    else{
        if(cursum >= ans){
            return;
        }
        else{
            for(i = 0; i < m; i++){
                if(!((i == v - 1) || (i == v) || (i == v + 1))){
                    dfs(k + 1, i, cursum + map[k][i]);
                }
            }
        }
    }
}
int main(){
    int n, i, j;
    scanf("%d", &n);
    while(n--){
        scanf("%d", &m);
        for(i = 0; i < m; i++){
            for(j = 0; j < m; j++){
                scanf("%d", &(map[i][j]));
            }
        }
        ans = 0x7fffffff;
        for(i = 0; i < m; i++){
            dfs(0, i, 0);
        }
        printf("%d\n", ans);
    }
    return 0;
}