给定 $k$ 个非空多重集，每个多重集仅包含绝对值不超过 $10^9$ 的整数。 要求从每个多重集中恰好选择一个数字，组成一个长度为 $k$ 的数组 $(a_1, a_2, \dots, a_k)$。 设 $d = \max(a_1, a_2, \dots, a_k) - \min(a_1, a_2, \dots, a_k)$，请计算 $d$ 的最小值。

输入格式

每个测试点包含多个测试用例。输入的第一行包含一个整数 $t$ ($1 \le t \le 10^6$)，表示测试用例的数量。接下来是各测试用例的描述。 每个测试用例的第一行包含一个整数 $k$ ($1 \le k \le 10^6$)，表示多重集的数量。 每个测试用例的接下来 $k$ 行，每行首先读入一个参数 $c_i$，表示第 $i$ 个多重集的大小，随后是 $c_i$ 个绝对值不超过 $10^9$ 的整数，表示第 $i$ 个多重集中的元素。 保证每个测试用例中 $\sum_{i=1}^k c_i$ 不超过 $10^6$，所有测试用例中 $\sum_{i=1}^k c_i$ 的总和不超过 $4 \times 10^6$。

输出格式

对于每个测试用例，输出一个整数，表示 $d$ 的最小值。

样例

输入格式 1

3
2
1 6
3 -7 7 10
4
9 -5 -9 2 8 5 4 3 3 8
2 10 8
1 -7
3 1 6 10
1
1 9

输出格式 1

1
15
0