Hãng Taxi Sài Gòn được yêu cầu chuyển giao các tạp chí đến N vị trí. Các vị trí được đánh số $L_1$, $L_2$,...,$L_n$. Hãng phân 3 xe cho dịch vụ này. Ở thời điểm 0: 3 xe và tạp chí ở L1. Các tạp chí sẵn có ở L1, các xe có thể lấy số lượng tuỳ ý, các tạp chí sẽ được giao đến tất cả các vị trí theo các qui tắc sau:

1. Các tạp chí sẽ được giao ở $L_i$ sau khi đã được giao ở $L_{i-1}$ với mọi i từ 2 đến n
2. Ở mọi thời điểm chỉ 1 trong 3 xe là được phép chạy, 2 xe khác nghỉ ở vị trí khác Thời gian đi từ $L_i$ đến $L_j$ (hoặc ngược lại) với bất kỳ xe nào là một số nguyên dương D[i,j]

Yêu cầu:

Tổ chức kế hoạch giao hàng cho các xe sao cho thời gian các tạp chí phân phát đến tất cả N vị trí là nhỏ nhất. Tính thời gian giao hàng nhỏ nhất.

Input:

Dữ liệu vào có cấu trúc: Dòng đầu số *M *(1 ≤ M ≤ 10) là số trường hợp test. Mỗi trường hợp bắt đầu là số nguyên dương n (n ≤ 30). Mỗi dòng i trong n-1 dòng tiếp theo chứa D[i,j]:i = 1,2,...,n-1; j = i+1,...,n; Các số cách nhau 1 khoảng trống.

Output:

Kết quả xuất ra chứa M dòng, mỗi dòng tương ứng 1 kết quả là thời gian nhỏ nhất để giao các tạp chí đến n vị trí.

Ví dụ:

INPUT

1
5
10 20 3 4
5 10 20
8 18
19

OUTPUT

22