金坷垃生產基地

題目敘述

就像之前提到的，美國聖地牙哥國際農業集團有好幾個金坷垃生產基地。卦長這天受邀參訪該集團，美國聖地牙哥國際農業集團總裁威廉伯爵告訴卦長集團一共有$n$間金坷垃生產基地，任兩間金坷垃生產基地之間都有一條道路相連。卦長想從第$1$間金坷垃生產基地開始，拜訪過其他$n-1$間金坷垃生產基地再回到起點，而且他希望一間金坷垃生產基地恰好拜訪過一次，中途也不能回到第$1$間金坷垃生產基地，請問他最少需要走多長的距離呢?

輸入說明

第一行有一個整數$T$，表示共有幾筆測資。接著每筆測資第一行為一正整數$n$，表示有$n$間金坷垃生產基地。接著有$n-1$行表示兩金坷垃生產基地的距離，第$i$行共有$n-i-1$個非負整數，依序表示「第$i$間金坷垃生產基地到第$i+1$間金坷垃生產基地的距離」、「第$i$間金坷垃生產基地到第$i+2$間金坷垃生產基地的距離」…「第$i$間金坷垃生產基地到第$n$間金坷垃生產基地的距離」。

輸出說明

對於每筆測資輸出卦長需要走的最短距離

範例輸入

2
3
1 2
3
4
1 3 6
2 5
4

範例輸出

6
13

配分方法

• 0% 範例測資
• 40% $n \leq 10$
• 60% $n \leq 16$

Hints

Judge Setting