#include <iostream>
using namespace std;

int final=0;
int n;

void search(int **arr,int f,int s,int count,int sum)
{
    sum+=arr[f][s];

    if(f==2*n-2) //마지막 숫자에 도달했을 때
    {
        if(final < sum)final = sum; 
        return;
    }

    if(f<n-1)
    {
        search(arr,f+1,s,count,sum);
        search(arr,f+1,s+1,count,sum);
    }
    else // 역삼각형 모양일때
    {
        if(s==0) search(arr,f+1,s,count,sum);
        else if(s==f-(2*count))
        {
            search(arr,f+1,f+1-(2*(count+1)),count+1,sum);
        }
        else
        {
            search(arr,f+1,s-1,count+1,sum);
            search(arr,f+1,s,count+1,sum);
        }
    }
}

int main()
{
    int cases=0;
    cin >> cases;
    for(int i=0; i<cases; i++)
    {
        int count=1;
        final=0;

        cin >> n;

        int **arr= new int*[2*n-1];

        for(int j=0; j<2*n-1; j++) //다이아몬드 입력
        {
            if(j<n)
            {
                arr[j] = new int[j+1];
                for(int k=0; k<j+1; k++)
                {
                    cin>>arr[j][k];
                }
            }
            else
            {
                arr[j] = new int[j-(2*count-1)];
                for(int k=0; k<j-(2*count-1); k++)
                {
                    cin>>arr[j][k];
                }
                count++;
            }
        }

        search(arr,0,0,0,0);

        cout<<final<<endl;

    }
}