#include <iostream>
using namespace std;

int main() {
 // your code goes here
 int a, b, arr[98][98], i, j, count=0, i_temp, j_temp, max, max1, max2;
 cin>>a;
 while(a--) {
  arr[98][98]=0;
  cin>>b;
  count=0;
  for(i=0; i<b; i++) {
   if(count<b) count++;
   for(j=0; j<count; j++) {
    cin>>arr[i][j];
   }
  }
  i_temp=i, j_temp=j;
  for(; i>0; i--) {
    j=j_temp;
    for(; j>0; j--) {
        max1=arr[i][j-1]+arr[i-1][j-1], max2=arr[i][j]+arr[i-1][j-1];
        if(max1>max2) max=max1; else max=max2;
        arr[i-1][j-1]=max;
    }
    j_temp=j_temp-1;
  }
  cout<<arr[0][0]<<endl;
  //arr[100][100]=0;
 }
 return 0;
}