import java.io.*;
import java.util.Arrays;
import java.io.*;
 
 
class SumInTriangle {
    public static void main(String args[]) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int[][] arr=new int[100][100];
 
    int testcases =Integer.parseInt(br.readLine());
 
    while(testcases>0)
    {
 
        int n = Integer.parseInt(br.readLine());
        for(int i=0;i<n;i++)
        {
            String input=br.readLine();
            String s[]=input.split(" ");
            for(int j=0;j<=i;j++)
            arr[i][j]= Integer.parseInt(s[j]);
        }
    for(int i=n-2;i>=0;i--)
    {
    for(int j=0;j<=i;j++)
    {
    arr[i][j]+=arr[i+1][j]>arr[i+1][j+1]?arr[i+1][j]:arr[i+1][j+1];
    }
    }
    System.out.printf("%d\n",arr[0][0]);
    testcases--;
    }
 
 
    }
 
}

aW1wb3J0IGphdmEuaW8uKjsKaW1wb3J0IGphdmEudXRpbC5BcnJheXM7CmltcG9ydCBqYXZhLmlvLio7CiAKIApjbGFzcyBTdW1JblRyaWFuZ2xlIHsKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZyBhcmdzW10pIHRocm93cyBJT0V4Y2VwdGlvbnsKICAgIEJ1ZmZlcmVkUmVhZGVyIGJyID0gbmV3IEJ1ZmZlcmVkUmVhZGVyKG5ldyBJbnB1dFN0cmVhbVJlYWRlcihTeXN0ZW0uaW4pKTsKICAgIGludFtdW10gYXJyPW5ldyBpbnRbMTAwXVsxMDBdOwogCiAgICBpbnQgdGVzdGNhc2VzID1JbnRlZ2VyLnBhcnNlSW50KGJyLnJlYWRMaW5lKCkpOwogCiAgICB3aGlsZSh0ZXN0Y2FzZXM+MCkKICAgIHsKIAogICAgICAgIGludCBuID0gSW50ZWdlci5wYXJzZUludChici5yZWFkTGluZSgpKTsKICAgICAgICBmb3IoaW50IGk9MDtpPG47aSsrKQogICAgICAgIHsKICAgICAgICAgICAgU3RyaW5nIGlucHV0PWJyLnJlYWRMaW5lKCk7CiAgICAgICAgICAgIFN0cmluZyBzW109aW5wdXQuc3BsaXQoIiAiKTsKICAgICAgICAgICAgZm9yKGludCBqPTA7ajw9aTtqKyspCiAgICAgICAgICAgIGFycltpXVtqXT0gSW50ZWdlci5wYXJzZUludChzW2pdKTsKICAgICAgICB9CiAgICBmb3IoaW50IGk9bi0yO2k+PTA7aS0tKQogICAgewogICAgZm9yKGludCBqPTA7ajw9aTtqKyspCiAgICB7CiAgICBhcnJbaV1bal0rPWFycltpKzFdW2pdPmFycltpKzFdW2orMV0/YXJyW2krMV1bal06YXJyW2krMV1baisxXTsKICAgIH0KICAgIH0KICAgIFN5c3RlbS5vdXQucHJpbnRmKCIlZFxuIixhcnJbMF1bMF0pOwogICAgdGVzdGNhc2VzLS07CiAgICB9CiAKIAogICAgfQogCn0=

MgozCjEKMiAxCjEgMiAzCjQKMQoxIDIKNCAxIDIKMiAzIDEgMQ==

2
3
1
2 1
1 2 3
4
1
1 2
4 1 2
2 3 1 1