잡지 배달

테헤란의 한 택배 회사가 잡지를 테헤란의 $N$개 장소로 배달해야 한다. 장소는 $L_1$부터 $L_N$까지 번호가 매겨져 있다. 회사는 이 배달에 자동차 3대를 투입한다. 시각 $0$에 자동차 3대와 잡지는 모두 $L_1$에 있다. $L_1$에는 잡지가 충분히 있어 자동차는 원하는 만큼 실을 수 있다. 모든 장소에 잡지 한 부씩을 배달해야 하며, 다음 규칙을 지켜야 한다.

• 모든 $i = 2, \dots, N$에 대해, $L_i$로의 배달은 $L_{i-1}$로의 배달이 끝난 뒤에만 이루어질 수 있다.
• 어느 순간에도 자동차 3대 중 오직 한 대만 이동할 수 있고, 나머지 두 대는 각자의 장소에서 멈춰 있다.

자동차 한 대가 $L_i$와 $L_j$ 사이를 (어느 방향으로든) 이동하는 데 걸리는 시간은 양의 정수 $D_{i,j}$이다.

모든 $N$개 장소에 배달이 완료되는 시각이 최소가 되도록 배달 일정을 짜야 한다. 그 최소 완료 시각을 구하는 프로그램을 작성하라.

입력에는 이 문제의 인스턴스가 $M$개 들어 있다 ($1 \le M \le 10$). 첫 줄에 $M$이 주어진다. 각 인스턴스가 차례로 이어진다.

각 인스턴스의 첫 줄에는 $N$이 주어진다 ($N \le 30$). 이어지는 $N-1$개의 줄 중 $i$번째 줄($i = 1, \dots, N-1$)에는 $j = i+1, \dots, N$에 대한 $D_{i,j}$ 값들이 공백으로 구분되어 주어진다. 거리는 대칭이다($D_{i,j} = D_{j,i}$).

각 인스턴스마다 한 줄씩, 총 $M$개의 줄을 출력한다. 각 줄에는 해당 인스턴스에서 모든 $N$개 장소에 잡지를 배달하는 데 걸리는 최소 시간을 출력한다.