#include <cstdio>
#include <cstdlib>

using namespace std;

int linhas;
int colunas;
int n;
int entrada;

int matriz[500][500];
int marcado[500][500];
int matrizCusto[500][500];

int dx[] = {0, 0, -1 , 1};
int dy[] = {1, -1 , 0, 0};

typedef struct no No;

struct no{
    int i;
    int j;
    int custo;
};

No heap[250000];

void insercao(int i, int j, int custo){
    heap[entrada].i = i;
    heap[entrada].j = j;
    heap[entrada].custo = custo;
    entrada++;
}

void heapify(int n, int i)
{
    int maior;
    No aux;
    while(i <= n/2)
    {
        if(n%2 == 0)
        {
            if(i < n/2)
            {
                if(heap[2*i].custo > heap[2*i+1].custo)
                {
                    maior = 2*i;
                }
                else
                {
                    maior = 2*i+1;
                }
            }
            else
            {
                maior = 2*i;
            }
        }
        else
        {
            if(i <= n/2)
            {
                if(heap[2*i].custo > heap[2*i+1].custo)
                {
                    maior = 2*i;
                }
                else
                {
                    maior = 2*i+1;
                }
            }
            else
            {
                maior = 2*i;
            }
        }

        if(heap[i].custo < heap[maior].custo)
        {
            aux = heap[i];
            heap[i] = heap[maior];
            heap[maior] = aux;
            i = maior;
        }
        else
            i = n;
    }
}

void constroiHeap(int n)
{
    int i;
    for(i = n/2; i >= 1; i--)
        heapify(n, i);
}

void heapS(int n)
{
    int i, j, k;
    int tam = n;
    No aux;
    for(i = n, j = 1; i >= 1; i--)
    {
        constroiHeap(tam);
        aux = heap[i];
        heap[i] = heap[j];
        heap[j] = aux;
        tam--;
    }
}

void formiga(){
    entrada = 1;
    for (int i = 0; i < linhas; ++i)
    {
        for (int j = 0; j < colunas; ++j)
        {
            marcado[i][j] = false;
            matrizCusto[i][j] = 1<<30;
        }
    }

    insercao(0, 0, matriz[0][0]);

    int i;
    int j;
    int custo=0;
    int custoTotal = 0;
    int k;

    i = heap[1].i;
    j = heap[1].j;
    custo = heap[1].custo;
    entrada--;

    while(1){
        if(entrada > 2) heapS(entrada-1);

        i = heap[1].i;
        j = heap[1].j;
        custo = heap[1].custo;


        if(entrada > 2){ // tira do heap
            heap[1].i = heap[entrada-1].i;
            heap[1].j = heap[entrada-1].j;
            heap[1].custo = heap[entrada-1].custo;
            entrada--;
        }


        if(marcado[i][j])
            continue;

        marcado[i][j] = true;

        if(i == linhas - 1 && j == colunas - 1) break;


        //erro aqui!
        for (int cont = 0; cont < 4; ++cont)
        {
            if((j+dx[cont] >= 0 && j+dx[cont] < colunas) && (i+dy[cont] >= 0 && i+dy[cont] < linhas)){
                if(!marcado[i+dy[cont]][j+dx[cont]] && custo+matriz[i+dy[cont]][j+dx[cont]] < matrizCusto[i+dy[cont]][j+dx[cont]]){
                    insercao(i+dy[cont], j+dx[cont], custo+matriz[i+dy[cont]][j+dx[cont]]);
                }
            }
        }

    }

    /*for (int i = 0; i < linhas; ++i)
    {
        for (int j = 0; j < colunas; ++j)
        {
            printf("%d ", matrizCusto[i][j]);
        }
        printf("\n");
    }*/

    printf("%d\n", custo);


}

int main()
{
    freopen("input", "r", stdin);

    scanf("%d", &n);
    while(n--){
        scanf("%d %d", &linhas, &colunas);
        for (int i = 0; i < linhas; ++i)
        {
            for (int j = 0; j < colunas; ++j)
            {
                scanf("%d", &matriz[i][j]);
            }
        }



        formiga();
    }
    return 0;
}