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