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