using System;
using System.Collections.Generic;
using System.Text;
namespace CodeChefConsoleApplication
{
class SumsInATriangle
{
static void Main(string[] args)
{
short n = short.Parse(Console.ReadLine());
StringBuilder sb = new StringBuilder();
while (n-- > 0)
{
int lines = Int32.Parse(Console.ReadLine());
int[] row = new int[lines];
for (int i = 0; i < lines; i++)
{
int[] tempRow = new int[lines];
string str = Console.ReadLine();
int j = 0;
foreach (String sub in str.Split(' '))
{
int element = Int32.Parse(sub);
tempRow[j] = Math.Max(element + getElement(row, j), element + getElement(row, j - 1));
j++;
}
row = tempRow;
}
int max = Int32.MinValue;
foreach (int t in row)
if (t > max)
max = t;
sb.Append(max);
if (n > 0)
sb.Append("\n");
}
Console.WriteLine(sb);
}
private static int getElement(int[] list, int p)
{
if (p < 0 || p >= list.Length || list.Length == 0)
return 0;
else
return list[p];
}
}
}

dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKdXNpbmcgU3lzdGVtLlRleHQ7Cm5hbWVzcGFjZSBDb2RlQ2hlZkNvbnNvbGVBcHBsaWNhdGlvbgp7CmNsYXNzIFN1bXNJbkFUcmlhbmdsZQp7CnN0YXRpYyB2b2lkIE1haW4oc3RyaW5nW10gYXJncykKewpzaG9ydCBuID0gc2hvcnQuUGFyc2UoQ29uc29sZS5SZWFkTGluZSgpKTsKU3RyaW5nQnVpbGRlciBzYiA9IG5ldyBTdHJpbmdCdWlsZGVyKCk7CndoaWxlIChuLS0gPiAwKQp7CmludCBsaW5lcyA9IEludDMyLlBhcnNlKENvbnNvbGUuUmVhZExpbmUoKSk7CmludFtdIHJvdyA9IG5ldyBpbnRbbGluZXNdOwpmb3IgKGludCBpID0gMDsgaSA8IGxpbmVzOyBpKyspCnsKaW50W10gdGVtcFJvdyA9IG5ldyBpbnRbbGluZXNdOwpzdHJpbmcgc3RyID0gQ29uc29sZS5SZWFkTGluZSgpOwppbnQgaiA9IDA7CmZvcmVhY2ggKFN0cmluZyBzdWIgaW4gc3RyLlNwbGl0KCcgJykpCnsKaW50IGVsZW1lbnQgPSBJbnQzMi5QYXJzZShzdWIpOwp0ZW1wUm93W2pdID0gTWF0aC5NYXgoZWxlbWVudCArIGdldEVsZW1lbnQocm93LCBqKSwgZWxlbWVudCArIGdldEVsZW1lbnQocm93LCBqIC0gMSkpOwpqKys7Cn0Kcm93ID0gdGVtcFJvdzsKfQppbnQgbWF4ID0gSW50MzIuTWluVmFsdWU7CmZvcmVhY2ggKGludCB0IGluIHJvdykKaWYgKHQgPiBtYXgpCm1heCA9IHQ7CnNiLkFwcGVuZChtYXgpOwppZiAobiA+IDApCnNiLkFwcGVuZCgiXG4iKTsKfQpDb25zb2xlLldyaXRlTGluZShzYik7Cn0KcHJpdmF0ZSBzdGF0aWMgaW50IGdldEVsZW1lbnQoaW50W10gbGlzdCwgaW50IHApCnsKaWYgKHAgPCAwIHx8IHAgPj0gbGlzdC5MZW5ndGggfHwgbGlzdC5MZW5ndGggPT0gMCkKcmV0dXJuIDA7CmVsc2UKcmV0dXJuIGxpc3RbcF07Cn0KfQp9

MgozCjEKMiAxCjEgMiAzCjQgCjEgCjEgMiAKNCAxIDIKMiAzIDEgMSA=

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