#include<iostream>
#include<cmath>
using namespace std;
 
int t,n,i;
short inp[5050] = {};
 
int sum_trian(int row,int column,int parent) {
	int index = ( (row-1)*row ) / 2 + column - 1;
	if( row==n )
		return (parent+inp[index]);
	parent += inp[index];
	return max(sum_trian(row+1,column,parent), sum_trian(row+1,column+1,parent));
}
 
int main() {
	cin >> t;
	while(t>0) {
		cin >> n;
		for(i=0;i<(n*(n+1)/2);i++)
		cin>>inp[i];
		cout << sum_trian(1,1,0) << endl;
		t--;
	}
	return 0;
}

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNtYXRoPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IHQsbixpOwpzaG9ydCBpbnBbNTA1MF0gPSB7fTsKCmludCBzdW1fdHJpYW4oaW50IHJvdyxpbnQgY29sdW1uLGludCBwYXJlbnQpIHsKCWludCBpbmRleCA9ICggKHJvdy0xKSpyb3cgKSAvIDIgKyBjb2x1bW4gLSAxOwoJaWYoIHJvdz09biApCgkJcmV0dXJuIChwYXJlbnQraW5wW2luZGV4XSk7CglwYXJlbnQgKz0gaW5wW2luZGV4XTsKCXJldHVybiBtYXgoc3VtX3RyaWFuKHJvdysxLGNvbHVtbixwYXJlbnQpLCBzdW1fdHJpYW4ocm93KzEsY29sdW1uKzEscGFyZW50KSk7Cn0KCmludCBtYWluKCkgewoJY2luID4+IHQ7Cgl3aGlsZSh0PjApIHsKCQljaW4gPj4gbjsKCQlmb3IoaT0wO2k8KG4qKG4rMSkvMik7aSsrKQoJCWNpbj4+aW5wW2ldOwoJCWNvdXQgPDwgc3VtX3RyaWFuKDEsMSwwKSA8PCBlbmRsOwoJCXQtLTsKCX0KCXJldHVybiAwOwp9