import psyco
psyco.full()
class matrix: #class1
def __init__(self,no_of_rows):
self.no_of_rows=no_of_rows
self.matrix=[]*(self.no_of_rows)
def fill_matrix(self):
for i in range(self.no_of_rows):
row=input().split()
for j in range(len(row)):
row[j]=int(row[j])
self.matrix.append(row)
class problem_solution(matrix): #class2
def __init__(self,class1):
self.no_of_rows=class1.no_of_rows
self.matrix=class1.matrix
self.table_matrix=[None]*(class1.no_of_rows+1)
for i in range(class1.no_of_rows+1):
self.table_matrix[i]=[None]*(class1.no_of_rows+1)
def solve(self,i,j):
if(self.table_matrix[i][j] != None):
return self.table_matrix[i][j]
elif i>self.no_of_rows:
self.table_matrix[i][j]=0
return 0
else:
try:
sum1=self.solve(i+1,j)
sum2=self.solve(i+1,j+1)
sum3=self.matrix[i][j]+max(sum1,sum2)
return sum3
except:
self.table_matrix[i][j]=0
return 0
def main():
test_cases=int(input())
for i in range(test_cases):
no_of_rows=int(input())
new_matrix=matrix(no_of_rows)
new_matrix.fill_matrix()
solution=problem_solution(new_matrix)
print(solution.solve(0,0))
if __name__=='__main__':
main()