using System;
class prog
{
public static void Main(String[] args)
{
prog p = new prog();
int ctr = 0;
int t_cases = int.Parse(Console.ReadLine());
int[] res = new int[t_cases];
while (t_cases-- > 0)
{
int lines = int.Parse(Console.ReadLine());
int rows = 1;
int[][] ip = new int[lines][];
for (int i = 0; i < lines; i++)
{
ip[i] = new int[rows];
string inp = Console.ReadLine();
string[] sp = inp.Split(’ ');
for (int j = 0; j < sp.Length; j++)
ip[i][j] = int.Parse(sp[j]);
rows++;
}
for (int i = lines - 2; i >= 0; i–)
{
for (int j = 0; j < i + 1; j++)
ip[i][j] = ip[i][j] + p.max(ip[i + 1][j], ip[i + 1][j + 1]);
}
rows = 1;
res[ctr] = ip[0][0];
ctr++;
}
foreach(int s in res)
Console.WriteLine(s.ToString());
}
int max(int a, int b)
{
if (a > b)
return a;
else if (a < b)
return b;
return a;
}
}