Simple Set Problem

Problem Description

Given $k$ non empty multiple sets, each multiple set only contains integers with absolute values not exceeding $10^{9}$. It is required to select exactly one number from each multiple set to form an array $(a_1,a_2,\dots,a_k)$ with a length of $k$. Assuming $d=\max(a_1, a_2,\dots,a_k) - \min(a_1, a_2,\dots,a_k)$.Please calculate the minimum $d$.

Input

Each test contains multiple test cases.The first line of input contains a single integer $t (1 \leq t \leq 10^{6})$---the number of test cases.The description of test cases follows. The first line of each test case contains a single integer $k(1 \leq k \leq 10^{6})$ —— the number of multiple sets. The following $k$ lines of each test case first read in a parameter $c_i$ —— indicating the size of the $i$-th multiple set, followed by $c_i$ integers with absolute values not exceeding $10^{9}$ —— indicating the elements of the $i$-th multiple set. Guarantee that $\sum_{i=1}^{k}{c_i}$ for each test case does not exceed $10^{6}$, the sum of $\sum_{i=1}^{k}{c_i}$ for all test cases does not exceed $4\times 10^{6}$.

Output

For each testcase, output an integer representing the answer, which is the minimum $d$.

Sample Input

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

Sample Output

1
15
0

Source

2023“钉耙编程”中国大学生算法设计超级联赛（4）