Условие

---

ЗАДАЧА I. БЕНЗИНОСТАНЦИИ
---
Фирма има N бензиностанции. Всяка седмица нейна цистерна извършва зареждането им тръгвайки от нейната централна складова база за горива, минавайки през всички бензиностанции и връщайки се обратно в нея. Помогнете на шофьора на цистерната да пресметне дължината на най-краткия път, по който той да извърши зареждането.

Входни данни: 
На първият ред ще получите броя на тестовете – Т. На първият ред от всеки тест ще получите броя на бензиностанциите N (централната база не се включва в N). На следващият ред ще получите най-кратките разстояния S(0,j) от централната база до всички бензиностанции, подредени по нарастващ ред на номерата на бензиностанциите. На следващите N – 1 реда ще получите най-кратките разстоянията S(k,j) от поредната  бензиностанция K (започвайки от първата във възходящ ред) до всички останали N – K бензиностанции с по-голям номер, подредени по нарастващ ред на номерата на бензиностанциите. Всички пътища са двупосочни. Не е възможно от една бензиностанция да стигнем до друга за по кратък път от този, който е зададен в тестовите данни за съответната двойка бензиностанции.

Ограничения:
1 ≤ Т ≤ 10
1 ≤ N ≤ 17
1 ≤ S(i,j) (разстояние между две бензиностанции – цяло число) ≤ 1500

Изходни данни: 
За всеки тест изведете на отделен ред дължината на най-краткия път, по който можем да минем през всички бензиностанции, започвайки от централната база и завършвайки пак в нея.

Примерен вход:
1
4
11 13 22 7
15 18 17
11 11
22	

Примерен изход:
58

Коментар на примера: Най-краткият маршрут минава през бензиностанциите 1, 3, 2 и 4 и е с дължина 11 + 18 + 11 + 11 + 7 = 58