题目描述

给定 $n$ 个数组 $a_1,a_2,\ldots,a_n$。

你需要恰好执行一次如下操作：

• 选择一个数组 $a_i$。
• 选择该数组中的一个元素 $a_{i,j}$。
• 选择另一个不同的数组 $a_k$。
• 将 $a_{i,j}$ 加到 $a_k$ 的末尾，然后从 $a_i$ 中删除它。

一次操作 $(i,j,k)$ 的价值定义为操作完成后所有数组的 $\operatorname{MEX}$ 之和，即

请计算所有可能的不同且相互独立的操作的价值之和。若有序三元组 $(i,j,k)$ 不同，则两个操作不同。

$\operatorname{MEX}(a)$ 定义为数组中没有出现的最小非负整数。

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试数据第一行包含一个整数 $n$，表示数组个数。

接下来 $n$ 行，第 $i$ 行先包含一个整数 $l_i$，表示第 $i$ 个数组长度，随后包含 $l_i$ 个整数表示该数组。

保证所有测试数据的 $l_i$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每组测试数据，输出所有可能操作的价值之和。

样例

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

6
0
50
8
43
19202

样例说明

第一组测试数据有 $3$ 种不同操作：

• 将第一个数组中的 $0$ 移到第二个数组，得到 $[]$ 和 $[0,1,2]$，价值为 $0+3=3$。
• 将第二个数组中的 $1$ 移到第一个数组，得到 $[0,1]$ 和 $[2]$，价值为 $2+0=2$。
• 将第二个数组中的 $2$ 移到第一个数组，得到 $[0,2]$ 和 $[1]$，价值为 $1+0=1$。

第二组测试数据中没有任何数组包含 $0$，所有操作价值均为 $0$。

数据范围

• $1 \le t \le 10^4$
• $2 \le n \le 2\cdot 10^5$
• $1 \le l_i \le 10^5$
• $0 \le a_{i,j} \le 10^6$
• 所有测试数据的 $l_i$ 之和不超过 $2\cdot 10^5$

来源

Codeforces Round 1074 (Div. 4), Problem G - Mixing MEXes