#include <stdio.h>
#include <stdlib.h>
typedef struct tipo
{
    int linha;
    int coluna;
    int custo;
}Tipo;
int Tamanho;
void Heapify (Tipo*vetor,int tamanho,int  i)
{
    int menor;
    Tipo*temp=(Tipo*)malloc(sizeof(Tipo));
    while(i<=tamanho/2)
    {
        if(i<(tamanho/2+tamanho%2))
        {
            if(vetor[2*i].custo<vetor[2*i+1].custo)
            {
                menor=2*i;
            }
            else
            {
                menor=2*i+1;
            }
        }
        else
        {
            menor=2*i;
        }
        if(vetor[i].custo>vetor[menor].custo)
        {
            temp->coluna=vetor[i].coluna;
            temp->linha=vetor[i].linha;
            temp->custo=vetor[i].custo;
            ///
            vetor[i].linha=vetor[menor].linha;
            vetor[i].coluna=vetor[menor].coluna;
            vetor[i].custo=vetor[menor].custo;
            ///
            vetor[menor].coluna=temp->coluna;
            vetor[menor].linha=temp->linha;
            vetor[menor].custo=temp->custo;
            i=menor;
        }
        else
        {
            i=tamanho;
        }

    }
    free(temp);
}
void constroi(Tipo*vetor,int tamanho)
{
    int i;
    for(i=tamanho/2;i>=1;i--)
    {
        Heapify (vetor,tamanho,i);
    }
}
Tipo* Remove(Tipo*heap)
{
    heap[1]=heap[Tamanho];///o primeiro recebe o ultimo elemento e diminui o tamanho
    Tamanho--;
    constroi(heap,Tamanho);///faz heapfy
    return heap;
}
void Imprime(Tipo*heap)
{
    int i;
    for(i=1;i<=Tamanho;i++)
    {
        printf("x= %d,y= %d e custo =%d\n",heap[i].linha,heap[i].coluna,heap[i].custo);
    }
}
int main()
{
   FILE*entrada=fopen("L4Q3.in","r");
   FILE*saida=fopen("L4Q3.out","w");
   int i,j,qtd,contador;
   fscanf(entrada,"%d",&qtd);
   contador=0;
   int linhas,colunas;
   int matriz[600][600];
   int marcado[600][600];
   Tipo*vetor;//pra heap
   int dx[4]= {0,0,-1,1};
   int dy[4]= {1,-1,0,0};
   int x,y;
   int c;
   //int tamanho;
   int destinox,destinoy;
   while(contador<qtd)
   {
       printf("%d\n",contador);
       Tamanho=1;
       //tamanho=1;
       contador++;
       fscanf(entrada,"%d %d",&linhas,&colunas);
       destinox=linhas-1;
       destinoy=colunas-1;
       for(i=0;i<linhas;i++)
       {
           for(j=0;j<colunas;j++)
           {
               fscanf(entrada,"%d",&matriz[i][j]);
               //printf("%d\n",matriz[i][j]);
               marcado[i][j]=0;
           }
       }
       vetor=(Tipo*)malloc(sizeof(Tipo)*(10000));
       vetor[1].linha=0;
       vetor[1].coluna=0;
       vetor[1].custo=matriz[0][0];
       while(vetor[1].linha!=destinox || vetor[1].coluna!=destinoy)
       {
           //printf("contador eh %d\n",contador);
           //Imprime(vetor);
           ///tira do heap
           x=vetor[1].linha;
           y=vetor[1].coluna;
           c=vetor[1].custo;
           //printf("depois de remover\n");
           vetor=Remove(vetor);
           //Tamanho--;
           //Imprime(vetor);
           //printf("eu tou em %d\n",matriz[x][y]);
           marcado[x][y]=1;///marca
           for (i=0; i<4; i++)
            {
                if (x+dx[i]>=0 && y+dy[i]>=0)
                {
                    if (x+dx[i]<linhas && y+dy[i]<colunas)
                    {
                        if (marcado[x+dx[i]][y+dy[i]]==0)
                        {
                            Tamanho++;
                            vetor[Tamanho].linha=x+dx[i];
                            vetor[Tamanho].coluna=y+dy[i];
                            vetor[Tamanho].custo=matriz[x+dx[i]][y+dy[i]]+c;
                        }
                    }
                }
            }
              constroi(vetor,Tamanho);
       }
       fprintf(saida,"%d\n",vetor[1].custo);
       free(vetor);


   }
    return 0;
}