#include<stdio.h>int max(int a,int b){	if(a>=b)		return a;		else			return b;}int main(){	int t,num,k,a[105][105];	scanf("%d",&t);	while(t--)	{		int sum=0;		scanf("%d",&num);		k=num;		while(num--)		{			for(int i=0;i<k;i++)			{	for(int j=0;j<k-num;j++)			scanf("%d",&a[i][j]);}		}		for(int i=k-1;i>=0;i--)		{			for(int j=0;j<i;j++)				a[i][j]=max(a[i+1][j],a[i+1][j+1]);			sum+=a[i][j];		}		printf("%d\n",sum);	}}