보안 업체

명우는 보안 업체 직원으로, 강남역 주변에 있는 여러 상점을 도보로 순찰하는 일을 맡고 있다.

강남역 일대는 하나의 직선(선분)으로 나타낼 수 있으며, 명우의 회사와 상점들은 왼쪽부터 차례로 이 직선 위의 점 $p_1, p_2, \dots, p_N$ 으로 표현된다. 회사는 $p_a$ 에 있고, 이 점을 시작점 $s = p_a$ 라고 한다. 명우는 $s$ 에서 순찰을 시작하여 모든 상점 $p_i$ 를 적어도 한 번씩 방문해야 한다.

이웃한 두 점 $p_i$ 와 $p_{i+1}$ 사이를 오가는 데 걸리는 시간은 $t[p_i, p_{i+1}]$ 이다. 점 $p_i$ 의 대기 시간 $\ell_i$ 는 시작점 $s$ 를 출발한 뒤 $p_i$ 에 처음 도착하기까지 걸린 시간이다. 시작점 $s = p_a$ 자신의 대기 시간 $\ell_a$ 는 $0$ 이다. 명우는 모든 상점의 대기 시간의 합이 최소가 되도록 순찰 경로를 정해야 한다.

예를 들어 상점이 $p_1$ 부터 $p_6$ 까지 $6$ 개 있고 시작점이 $s = p_3$ 이며, $t[p_1,p_2] = 7$, $t[p_2,p_3] = 4$, $t[p_3,p_4] = 1$, $t[p_4,p_5] = 2$, $t[p_5,p_6] = 9$ 라고 하자. 명우가 $s$ 에서 오른쪽으로 걷기 시작하면 대기 시간 $\ell_4$ 와 $\ell_5$ 는 각각 $1$ 과 $3$ 이 된다. 순찰 순서를 적절히 정하면 대기 시간의 합을 $71$ 로 만들 수 있으며, 이보다 더 작게 만드는 방법은 없다.

점의 개수 $N$ 과 이웃한 점들 사이의 이동 시간 $t[p_i, p_{i+1}]$ ($i = 1, \dots, N-1$) 이 주어질 때, 대기 시간의 합을 최소로 하는 값을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 각 테스트 케이스는 다음과 같이 구성된다.

• 첫째 줄에 상점의 수 $N$ ($1 \le N \le 100$) 이 주어진다.
• 둘째 줄에 시작점의 위치 $a$ ($1 \le a \le N$) 가 주어진다. $a$ 번째 점 $p_a = s$ 가 시작점이다.
• 이어지는 $N-1$ 개의 줄 중 $i$ 번째 줄에는 $t[p_i, p_{i+1}]$ ($1 \le t[p_i, p_{i+1}] \le 15\,000\,000$) 이 주어진다.

각 테스트 케이스마다 모든 상점을 순찰하는 모든 방법 중 대기 시간의 합의 최솟값을 한 줄에 하나씩 출력한다.