You are given $$$n$$$ arrays $$$a_1, a_2, \ldots, a_n$$$.

The following operation is performed exactly once:

Choose any array among $$$a_1, a_2, \ldots, a_n$$$. Suppose you've chosen array $$$a_i$$$ ($$$1 \leq i \leq n$$$).
Choose any element in array $$$a_i$$$. Suppose you've chosen the $$$j$$$-th element of $$$a_i$$$, denoted by $$$a_{i,j}$$$ ($$$1 \leq j \leq |a_i|$$$, where $$$|a_i|$$$ denotes the length of array $$$a_i$$$).
Choose any other array among $$$a_1, a_2, \ldots a_n$$$ that is not $$$a_i$$$. Suppose you've chosen $$$a_k$$$ ($$$1 \leq k \leq n, k \neq i$$$).
Add $$$a_{i,j}$$$ to the back of array $$$a_k$$$. Then, remove $$$a_{i,j}$$$ from $$$a_i$$$.
The value of this operation $$$(i,j,k)$$$ is defined as the sum of each array's $$$\operatorname{MEX}$$$ after the operation is performed. More formally, the value of an operation after the operation is performed is $$$\sum_{i=1} ^{n} \operatorname{MEX}(a_i)$$$.

Evaluate the sum of the values of all possible distinct independent operations. Two operations are distinct if the ordered triple of integers $$$(i,j,k)$$$ is different.

$$$\operatorname{MEX}(a)$$$ is defined as the smallest non-negative integer that is not present in the array. For example, $$$\operatorname{MEX}([1, 2, 0, 5])$$$ is $$$3$$$, and $$$\operatorname{MEX}([1, 2, 4, 9])$$$ is $$$0$$$.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of arrays.

The next $$$n$$$ lines start with $$$l_i$$$ ($$$1 \le l_i \le 10^5$$$) — the length of the $$$i$$$th array — then contain $$$l_i$$$ integers $$$a_1, a_2, \ldots, a_{l_i}$$$ ($$$0 \le a_{i_j} \le 10^6$$$) — the array $$$a_i$$$.

It is guaranteed that the sum of $$$l_i$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output the sum of the values of all possible distinct operations.

Note

For the first test case, we have 3 possible distinct operations:

$$$i = 1, j = 1, k = 2$$$: The arrays are now [] and [$$$0, 1, 2$$$], which have a $$$\operatorname{mex}$$$ of $$$0$$$ and $$$3$$$ respectively, so the value of the operation is $$$3$$$.
$$$i = 2, j = 1, k = 1$$$: The arrays are now [$$$0, 1$$$] and [$$$2$$$], which have a $$$\operatorname{mex}$$$ of $$$2$$$ and $$$0$$$ respectively, so the value of the operation is $$$2$$$.
$$$i = 2, j = 2, k = 1$$$: The arrays are now [$$$0, 2$$$] and [$$$1$$$], which have a $$$\operatorname{mex}$$$ of $$$1$$$ and $$$0$$$ respectively, so the value of the operation is $$$1$$$.

For the second test case, since no array contains a zero, the value of all operations will be $$$0$$$.

Mixing MEXes

Examples