#include <iostream>
#define INF 1000000

using namespace std;

int voa, bAct, it, m, n, aumento;

int* sol;
int* soa;
int* itAnterior;
int* mejorasAnteriores;
int** poblacion;

bool solucion(int nivel){
    return nivel<=m;
}

bool criterio(int nivel){
    return (nivel<m) && (n-it)>=(m-nivel);
}

bool masHermanos(int nivel){
    return sol[nivel]<=m;
}

void retroceder(int nivel){
    sol[nivel]=0;
    nivel--;
    it=itAnterior[nivel];
    aumento=mejorasAnteriores[nivel];
}

int mejora(int nivel){
    int cantidad = 0;
    for(int i=i; i<nivel; i++){
        cantidad += poblacion[sol[i]-1][it-1];
        cantidad += poblacion[it-1][sol[i]-1];
    }
    return cantidad;
}

void generar(int nivel){
    it++;
    bAct-=aumento;
    sol[nivel]=it;
    aumento=mejora(nivel);
    bAct-=aumento;
}

void inicializar_arrays(){
    for(int i=0; i<(m+1); i++){
        sol[i]=0;
        soa[i]=0;
        mejorasAnteriores[i]=0;
        itAnterior[i]=0;
    }
}

int backtracking(){
    int nivel = 1;
    voa = -INF;
    bAct = it = aumento = 0;
    inicializar_arrays();
    do{
        generar(nivel);
        if(solucion(nivel) && bAct>voa){
            voa = bAct;
            soa = sol;
        } else if(criterio(nivel)){
            mejorasAnteriores[nivel]=bAct;
            itAnterior[nivel] = it;
            nivel++;
            aumento=0;
        } else {
            while(!masHermanos(nivel)) retroceder(nivel);
        }
    } while(nivel==0);

    return voa;
}

void leerMatriz(){
    int k;
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++){
            cin >> k;
            poblacion[i][j] = k;
        }
    }
}

int main(int argc, char const *argv[]){

    int ncasos;
    cin >> ncasos;
    for(int k=0; k<ncasos; k++){
        cin >> n >> m;
        sol = new int[m+1];
        soa = new int[m+1];
        itAnterior = new int[m+1];
        mejorasAnteriores = new int[m+1];
        poblacion = new int*[n];
        for(int i=0; i<n; i++){
            poblacion[i]=new int[n];
        }

        leerMatriz();

        cout << backtracking() << "\n";


    }

}