VegiCat은 $k$개의 비어 있지 않은 팀에 속한 $n$명의 직원이 있는 회사를 소유하고 있습니다. 직원들은 수직선으로 나타내어지는 곧은 도로를 따라 살고 있습니다. VegiCat은 그들을 위해 두 개의 모임 장소를 마련하려고 합니다.

VegiCat은 각 팀이 정확히 하나의 집합에 속하도록 팀들을 두 집합 $A$와 $B$로 나눕니다. 그는 각 집합에 대해 임의의 실수 좌표에 모임 장소를 하나씩 선택합니다. 같은 팀의 모든 직원은 반드시 같은 모임 장소로 가야 합니다. 집합 $A$에 속한 각 팀은 $A$의 모임 장소로 가고, 집합 $B$에 속한 각 팀은 $B$의 모임 장소로 갑니다. 두 집합 중 어느 것이든 비어 있을 수 있습니다.

$A$에 속한 팀들의 모든 직원의 집 위치 목록을 $S_A$라 하고, $B$에 대해서도 비슷하게 $S_B$를 정의합시다. 집 위치가 겹치더라도 각 직원은 개별적으로 계산됩니다.

집 위치의 목록 $S = (x_1, x_2, \ldots, x_m)$에 대하여, 이 직원들이 하나의 모임 장소로 이동하는 최소 총 이동 거리는 다음과 같습니다:

$$M(S) = \min_{p \in \mathbb{R}} \sum_{j=1}^{m} |x_j - p|.$$

$S$가 비어 있을 때는 $M(S) = 0$으로 정의합니다. 팀들을 두 집합으로 나누는 모든 방법에 대해 $M(S_A) + M(S_B)$를 최소화할 수 있도록 VegiCat을 도와주세요.

입력

첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 $T$ ($1 \le T \le 3 \cdot 10^5$)가 주어집니다. 이어서 테스트 케이스의 설명이 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 직원의 수와 팀의 수를 각각 나타내는 두 정수 $n$과 $k$ ($1 \le k \le n \le 3 \cdot 10^5$)가 주어집니다.

다음 $k$개의 줄에는 각각 하나의 팀에 대한 정보가 주어집니다. $i$번째 줄에는 팀 $i$의 직원 수를 나타내는 정수 $m_i$ ($1 \le m_i \le n$)와, 이어서 그들의 집 위치를 나타내는 $m_i$개의 정수 $x_{i,1}, \ldots, x_{i,m_i}$ ($1 \le x_{i,j} \le 10^7$)가 주어집니다. 한 테스트 케이스에서 모든 $m_i$의 합은 $n$입니다.

집 위치는 중복될 수 있으며 임의의 순서로 주어질 수 있습니다.

모든 테스트 케이스에서 $n$의 합이 $3 \cdot 10^5$을 넘지 않음이 보장됩니다.

출력

각 테스트 케이스마다 가능한 최소 총 이동 거리를 나타내는 정수를 출력합니다.

예제

입력 1

2
4 2
2 1 3
2 8 10
8 3
3 4 12 1
2 3 2
3 9 8 10

출력 1

4
15

참고

첫 번째 테스트 케이스에서 VegiCat은 팀 $1$을 위치 $1$의 모임 장소로 보내고 팀 $2$를 위치 $8$의 모임 장소로 보냅니다. 각 팀의 직원들은 총거리 $2$만큼 이동하므로, 답은 $4$가 됩니다.

두 번째 테스트 케이스에서 VegiCat은 위치 $3$과 $9$에 모임 장소를 선택합니다. 그는 팀 $1$과 $2$를 첫 번째 모임 장소로 보내고, 팀 $3$을 두 번째 모임 장소로 보냅니다. 팀 $1$, $2$, $3$의 직원들은 각각 총거리 $12$, $1$, $2$만큼 이동하므로, 답은 $15$가 됩니다.