http://acm.hdu.edu.cn/showproblem.php?pid=2084

import java.util.Scanner;

public class Main {

    static Scanner input = new Scanner(System.in);
    static {

    }

    public static void main(String[] args) {
        int x = input.nextInt();
        for (int i = 0; i < x; i++) {
            int maxLevel = input.nextInt();
            int index = 0;
            Item[] items = new Item[(1 + maxLevel) * maxLevel / 2];
            for (int j = 1; j <= maxLevel; j++) {
                for (int j2 = 0; j2 < j; j2++, index++) {
                    items[index] = new Item(j, input.nextInt());
                }
            }

            for (int j = items.length - 1; j > -1; j--) {
                Item item = items[j];
                // has left at this level
                if (j - 1 >= 0 && items[j - 1].level == item.level) {
                    Item lastLevel = items[j - item.level];
                    if (lastLevel.result < lastLevel.num + item.result) {
                        lastLevel.result = lastLevel.num + item.result;
                    }
                }
                // has right at this level
                if (j + 1 < items.length && items[j + 1].level == item.level) {
                    Item lastLevel = items[j - (item.level - 1)];
                    if (lastLevel.result < lastLevel.num + item.result) {
                        lastLevel.result = lastLevel.num + item.result;
                    }
                }
            }

            System.out.println(items[0].result);

        }
    }

    static class Item {

        public Item(int level, int num) {
            this.level = level;
            this.num = num;
            this.result = num;
        }

        public int level;
        public int num;
        public int result = -1;
    }

}