공장 점검

유리는 러시아 여러 도시에 공장을 두고 있는 사업가다. 공장은 모두 한 달에 한 번씩 점검해야 한다. 유리는 자녀에게 사업을 가르치려고 점검을 맡기기로 했고, 조건을 두 가지 걸었다.

첫째, 자녀 한 명에게 서로 다른 공장을 두 개 이상 배정한다. 그래야 공장마다 운영 방식이 어떻게 다른지 비교해 볼 수 있다.

둘째, 이동 거리의 합이 가장 작아야 한다. 자녀는 배정받은 공장을 한 달에 한 번씩 모두 점검하고 출발한 공장으로 돌아온다. 그래서 자녀 한 명의 이동 거리는 배정받은 공장을 한 번씩 모두 지나 출발점으로 돌아오는 가장 짧은 순회 경로의 길이다. 공장 두 개를 배정받은 자녀는 두 공장 사이를 왕복하므로 이동 거리가 두 공장 사이 거리의 두 배다.

비용만 줄어든다면 유리는 자녀를 한 명만 써도 좋다고 생각한다. 예를 들어 공장이 네 개일 때, 한 명이 네 공장을 모두 도는 쪽이 더 짧은 배치도 있고, 두 명이 두 개씩 나눠 도는 쪽이 더 짧은 배치도 있다.

공장 사이의 거리가 주어질 때, 모든 공장을 점검하는 데 드는 이동 거리 합의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $m$이 주어진다.

각 테스트 케이스의 첫째 줄에는 공장의 개수 $n$이 주어진다 ($2 \le n \le 100$). 다음 $n-1$개 줄에는 공장 사이의 거리가 주어진다. 첫 줄에는 $n-1$개의 값이 있고, 차례대로 공장 1과 공장 $2, 3, 4, \dots, n$ 사이의 거리다. 둘째 줄에는 $n-2$개의 값이 있고, 차례대로 공장 2와 공장 $3, 4, \dots, n$ 사이의 거리다. 나머지 줄도 같은 방식이다.

모든 거리는 양의 정수이고, 두 공장 사이의 거리는 1000 이하다. 서로 다른 세 공장 사이의 거리는 삼각 부등식을 만족한다.

각 테스트 케이스마다 Case x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 이동 거리 합의 최솟값이다.

공장이 $n$개인 테스트 케이스에서 유리에게는 자녀가 항상 $n/2$명 이상 있다고 가정한다.