#include <stdio.h>
 
int n, a[100][100], cache[100][100];
 
int maxFromTop(int i, int j) {	
	if(i>n)
		return 0;
	if(cache[i][j]!=-1)
		return cache[i][j];
	int path1 = maxFromTop(i+1, j+1);
	int path2 = maxFromTop(i+1, j);
	int max = (path1>path2?path1:path2);
	cache[i][j] = a[i][j]+max;
	return a[i][j]+max;
}
 
int main(void) {
	int t, i, j;
	scanf("%d", &t);
	while(t--) {
		scanf("%d", &n);
		for(i=0; i<100; i++)
			for(j=0; j<100; j++)
				cache[i][j] = -1;
		for(i=0; i<n; i++)
			for(j=0; j<=i; j++)
				scanf("%d", &a[i][j]);
		printf("%d\n", maxFromTop(0, 0));
	}
	return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CgppbnQgbiwgYVsxMDBdWzEwMF0sIGNhY2hlWzEwMF1bMTAwXTsKCmludCBtYXhGcm9tVG9wKGludCBpLCBpbnQgaikgewkKCWlmKGk+bikKCQlyZXR1cm4gMDsKCWlmKGNhY2hlW2ldW2pdIT0tMSkKCQlyZXR1cm4gY2FjaGVbaV1bal07CglpbnQgcGF0aDEgPSBtYXhGcm9tVG9wKGkrMSwgaisxKTsKCWludCBwYXRoMiA9IG1heEZyb21Ub3AoaSsxLCBqKTsKCWludCBtYXggPSAocGF0aDE+cGF0aDI/cGF0aDE6cGF0aDIpOwoJY2FjaGVbaV1bal0gPSBhW2ldW2pdK21heDsKCXJldHVybiBhW2ldW2pdK21heDsKfQoKaW50IG1haW4odm9pZCkgewoJaW50IHQsIGksIGo7CglzY2FuZigiJWQiLCAmdCk7Cgl3aGlsZSh0LS0pIHsKCQlzY2FuZigiJWQiLCAmbik7CgkJZm9yKGk9MDsgaTwxMDA7IGkrKykKCQkJZm9yKGo9MDsgajwxMDA7IGorKykKCQkJCWNhY2hlW2ldW2pdID0gLTE7CgkJZm9yKGk9MDsgaTxuOyBpKyspCgkJCWZvcihqPTA7IGo8PWk7IGorKykKCQkJCXNjYW5mKCIlZCIsICZhW2ldW2pdKTsKCQlwcmludGYoIiVkXG4iLCBtYXhGcm9tVG9wKDAsIDApKTsKCX0KCXJldHVybiAwOwp9

MwozCjEKMiAxCjEgMiAzCjQgCjEgCjEgMiAKNCAxIDIKMiAzIDEgMSAKMwoxCjIgMQoxIDIgMwo=

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