#include <stdio.h>

int data[100][100];

int sumintr(int nr) {
	int r, col;
	for(r = nr - 1 - 1; r >= 0; --r) {
		for(col = 0; col <= r; ++col) {
			data[r][col] += data[r + 1][
			  data[r + 1][col] > data[r + 1][col + 1]
				? col
				: col + 1
			  ];
		}
	}

	return data[0][0];
}

int main() {
	int ns, nr, s, r, col;

	scanf("%d\n", &ns);
	for(s = 0; s < ns; ++s) {
		scanf("%d\n", &nr);
		for(r = 0; r < nr; ++r) {
			for(col = 0; col <= r; ++col)
				scanf("%d", &data[r][col]);
		}

		printf("%d\n", sumintr(nr));
	}
}