#!/usr/bin/perl

use strict;
use warnings;

my (@file, @tr, $prev, $cur, $f, $g);

{ local $/; @file = split ' ', scalar(<>); }

for (1..shift(@file)) {
    ($prev, @tr) =
        reverse
        map [ splice(@file, 0, $_) ],
        1..shift(@file);

    for $cur (@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

use strict;
use warnings;

my (@file, $rows, @tr, @prev, @cur, $f, $g);

{ local $/; @file = split ' ', scalar(<>); }

for (1..shift(@file)) {
    $rows = shift(@file);
    @tr = splice(@file, 0, $rows*($rows+1)/2);

    @prev = splice(@tr, -($rows--));

    while ($rows) {
        @cur = splice(@tr, -($rows--));

        $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

use strict;
use warnings;

my (@file, $rows, @tr, $prev, $cur, $f, $g);

{ local $/; @file = split ' ', scalar(<>); }

for (1..shift(@file)) {
    $rows = shift(@file);
    @tr = splice(@file, 0, $rows*($rows+1)/2);

    $prev = @tr - $rows--;

    while ($rows) {
        $cur = $prev - $rows--;

        $g = $tr[$prev];
        for (0 .. $rows) {
            $tr[$cur + $_] += ($f = $g) > ($g = $tr[$prev + $_ + 1])
                ? $f
                : $g;
        }

        $prev = $cur;
    }

    print "$tr[0]\n";
}