#!/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;
}