# include<iostream.h>
# include<stdio.h>
# include<string.h>
# include<math.h>
int con(char * ch)
{
	int len=strlen(ch),num=0;
	if(ch[0]=='x')
		return 100000;
	for(unsigned int i=0;i<strlen(ch);i++)
		num+=int(pow(10,double(len-1-i)))*(int(ch[i])-48);
	return num;
}

int main()
{
	int n,caseno;
	cin>>n;
	for(caseno=0;caseno<n;caseno++){
		int num,k,i,j;
		int cost[500][500]={0};
		cin>>num;
		
		for(i=1;i<num;i++){
			for(j=0;j<i;j++){
				char ch[100]={0};
				cin>>ch;
				int m=con(ch);
				cost[i][j]=m;
				cost[j][i]=m;
			}
		}

		for(k=0;k<num;k++){
			for(i=0;i<num;i++)
				for(j=0;j<num;j++)
					if(cost[i][j]>cost[i][k]+cost[k][j])
						cost[i][j]=cost[i][k]+cost[k][j];
		}
		
		int sum=0;
		for(j=1;j<num;j++){
			if(sum<cost[0][j])
				sum=cost[0][j];
		}
		cout<<sum<<endl<<endl;
	}
	return 0;
}