#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));
	}
}

##</code><code>##

#!/usr/bin/perl

for (1..<>) {
    @tr =
        map { [split ' ', <>] } 1 .. <>;

    $prev = pop @tr;
    for $cur (reverse @tr) {
        $g = $prev->[0];
        for (0 .. $#$cur) {
            $cur->[$_] += ($f = $g) > ($g = $prev->[$_ + 1])
                ? $f
                : $g;
        }

        $prev = $cur;
    }

    print "$prev->[0]\n";
}

##</code><code>##

#!/usr/bin/perl

undef $/; @file = split ' ', scalar <>;

for (1 .. shift(@file)) {
    $rows = $file[$cur++];

    @s = (0) x ($rows + 1);
    for (1 .. $rows) {
        ($i, $y) = (0, 0);
        $cur += $_ - 1;

        for ($cur .. $cur + $_ - 1) {
            $x = $y;
            $y = $s[$i];
            $s[$i++] = $file[$_] + ($x > $y ? $x : $y);
        }
    }

    $m = 0;
    $m = $m > $_ ? $m : $_ for @s;
    print "$m\n";

    $cur += $rows;
}