1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 int A[105][105],dp[105][105];
 5 int main(){
 6     int C,n;
 7     scanf("%d",&C);
 8     //&& scanf("%d",&n)!=EOF
 9     while(C-- ){
10         scanf("%d",&n);
11         memset(A,0,sizeof(A));
12         memset(dp,0,sizeof(dp));
13         for (int i=1;i<=n;i++)
14             for (int j=1;j<=i;j++){
15                 scanf("%d",&A[i][j]);
16                 A[i][0]=0;
17                 A[i][i+1]=0;
18             }
19         int maxx=0;
20         for (int i=1;i<=n;i++){
21             for (int j=1;j<=i;j++){
22                 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+A[i][j];
23             }
24         }
25         for (int i=n;i>=1;i--){
26             maxx=max(dp[n][i],maxx);
27         }
28         printf("%d
",maxx);
29     }
30     
31     return 0;
32 }