/*
- To change this template, choose Tools | Templates
- and open the template in the editor.
*/
package pract;
/**
*
-
@author dell
/
import java.io.;
import java.util.*;
class SumInTriangle
{
public static void main(String[] args) throws IOException
{
Scanner scn=new Scanner(System.in);
int tcase=scn.nextInt();
int[] res=new int[tcase];for(int k=1;k<=tcase;k++) { int rows=scn.nextInt(); int a[][]=new int[rows][]; for (int i = 0; i < rows; i++) { a[i]=new int[i+1]; for (int j = 0; j < i+1; j++) { a[i][j]=scn.nextInt(); } } for(int i=rows-2;i>=0;i--) { for(int j=i;j>=0;j--) { if(a[i+1][j]>a[i+1][j+1]) a[i][j]=a[i+1][j]+a[i][j]; else a[i][j]=a[i+1][j+1]+a[i][j]; } } res[k-1]=a[0][0]; } for (int i = 0; i < tcase; i++) { System.out.println(res[i]); }}
static class Scanner {
private final InputStream is;
private final byte[] data = new byte[0x2000];
private int next, size;
public Scanner(InputStream is) {
this.is = is;
}
private boolean read() throws IOException {
size = is.read(data);
if (size == 0) {
int i = is.read();
if (i < 0)
return false;
data[0] = (byte) i;
size = 1;
} else if (size < 0)
return false;
next = 0;
return true;
}
public int nextInt() throws IOException {
int r;
do {
if (next >= size && !read())
throw new EOFException();
r = data[next++];
} while (r < ‘0’ || r > ‘9’);
r -= ‘0’;
for (int d; (next < size || read()) && ‘0’ <= (d = data[next++])
&& d <= ‘9’
r = r * 10 + d - ‘0’;
return r;
}
}
}