G. Mixing MEXes
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Example
Input
6
2
1 0
2 1 2
3
1 1
2 2 3
3 4 5 6
5
4 1 7 8 10
2 5 6
2 0 7
2 6 6
2 6 8
2
1 3
3 0 1 2
2
6 0 0 1 2 2 3
3 0 2 3
10
1 0
9 7 8 0 1 5 6 4 3 2
8 4 3 8 6 2 5 0 1
7 2 3 0 1 0 4 0
2 3 1
9 2 0 5 4 1 3 0 0 0
7 6 3 2 4 1 8 0
5 3 2 4 1 0
4 0 3 1 1
3 0 3 2
Output
6
0
50
8
43
19202
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$$$.