VegiCat 拥有一家公司，共有 $n$ 名员工，分为 $k$ 个非空团队。员工们住在一条笔直的道路旁，该道路可以用数轴表示。VegiCat 想要为他们安排两个集合点。

VegiCat 将这些团队划分为两个集合 $A$ 和 $B$，每个团队恰好属于其中一个集合。他为每个集合在任意实数坐标处选择一个集合点。同一个团队的所有员工必须前往同一个集合点。 集合 $A$ 中的每个团队前往 $A$ 的集合点，集合 $B$ 中的每个团队前往 $B$ 的集合点。任一集合都可以为空。

令 $S_A$ 表示属于 $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$。请帮助 VegiCat 在将团队划分为两个集合的所有方式中，最小化 $M(S_A) + M(S_B)$。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 3 \cdot 10^5$），表示测试数据的组数。接下来是各组测试数据的描述。

每组测试数据的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 3 \cdot 10^5$），分别表示员工人数和团队数量。

接下来的 $k$ 行，每行描述一个团队。第 $i$ 行包含一个整数 $m_i$（$1 \le m_i \le n$），表示团队 $i$ 中的员工人数，随后是 $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$。