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