#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
int N;
 
int solution(vector <vector <int>> t, vector <vector <int>>& c, int x, int y)
{
	if (y == N - 1) return t[y][x];
	if (c[y][x] != 0) return c[y][x];
	int result = t[y][x] + max(solution(t, c, x, y + 1), solution(t, c, x + 1, y + 1));
	c[y][x] = result;
	return result;
}
 
int main(void)
{
	int C;
	cin >> C;
 
	while (C--)
	{
		cin >> N;
 
		vector <vector <int>> tri;
		vector <vector <int>> check(N, vector<int>(N, 0));
 
		for (int i = 0; i < N; i++)
		{
			vector <int> temp;
			for (int j = 0; j <= i; j++)
			{
				int input;
				cin >> input;
				temp.push_back(input);
			}
			tri.push_back(temp);
		}
 
		cout << solution(tri, check, 0, 0) << endl;
	}
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IE47CgppbnQgc29sdXRpb24odmVjdG9yIDx2ZWN0b3IgPGludD4+IHQsIHZlY3RvciA8dmVjdG9yIDxpbnQ+PiYgYywgaW50IHgsIGludCB5KQp7CglpZiAoeSA9PSBOIC0gMSkgcmV0dXJuIHRbeV1beF07CglpZiAoY1t5XVt4XSAhPSAwKSByZXR1cm4gY1t5XVt4XTsKCWludCByZXN1bHQgPSB0W3ldW3hdICsgbWF4KHNvbHV0aW9uKHQsIGMsIHgsIHkgKyAxKSwgc29sdXRpb24odCwgYywgeCArIDEsIHkgKyAxKSk7CgljW3ldW3hdID0gcmVzdWx0OwoJcmV0dXJuIHJlc3VsdDsKfQoKaW50IG1haW4odm9pZCkKewoJaW50IEM7CgljaW4gPj4gQzsKCgl3aGlsZSAoQy0tKQoJewoJCWNpbiA+PiBOOwoKCQl2ZWN0b3IgPHZlY3RvciA8aW50Pj4gdHJpOwoJCXZlY3RvciA8dmVjdG9yIDxpbnQ+PiBjaGVjayhOLCB2ZWN0b3I8aW50PihOLCAwKSk7CgoJCWZvciAoaW50IGkgPSAwOyBpIDwgTjsgaSsrKQoJCXsKCQkJdmVjdG9yIDxpbnQ+IHRlbXA7CgkJCWZvciAoaW50IGogPSAwOyBqIDw9IGk7IGorKykKCQkJewoJCQkJaW50IGlucHV0OwoJCQkJY2luID4+IGlucHV0OwoJCQkJdGVtcC5wdXNoX2JhY2soaW5wdXQpOwoJCQl9CgkJCXRyaS5wdXNoX2JhY2sodGVtcCk7CgkJfQoJCQoJCWNvdXQgPDwgc29sdXRpb24odHJpLCBjaGVjaywgMCwgMCkgPDwgZW5kbDsKCX0KfQ==

Mgo1CjYKMSAgMgozICA3ICA0CjkgIDQgIDEgIDcKMiAgNyAgNSAgOSAgNAo1CjEgCjIgNAo4IDE2IDgKMzIgNjQgMzIgNjQKMTI4IDI1NiAxMjggMjU2IDEyOA==

2
5
6
1  2
3  7  4
9  4  1  7
2  7  5  9  4
5
1 
2 4
8 16 8
32 64 32 64
128 256 128 256 128