你得到了 $$$n$$$ 数组 $$$a_1、a_2、\ldots、a_n$$$。
以下操作仅执行一次:
- 从 $$$a_1, a_2, \ldots, a_n$$$ 中选择任意数组。假设您选择了数组 $$$a_i$$$ ($$$1 \leq i \leq n$$$)。
- 选择数组 $$$a_i$$$ 中的任意元素。假设您选择了 $$$a_i$$$ 的第 $$$j$$$ 个元素,用 $$$a_{i,j}$$$ 表示($$$1 \leq j \leq |a_i|$$$,其中 $$$|a_i|$$$ 表示数组 $$$a_i$$$ 的长度)。
- 从 $$$a_1, a_2, \ldots a_n$$$ 中选择任何其他数组 不是 $$$a_i$$$。假设您选择了 $$$a_k$$$ ($$$1 \leq k \leq n, k \neq i$$$)。
- 将 $$$a_{i,j}$$$ 添加到数组 $$$a_k$$$ 的后面。然后,从 $$$a_i$$$ 中删除 $$$a_{i,j}$$$。
- 此操作 $$$(i,j,k)$$$ 的值被定义为执行操作后每个数组的 $$$\operatorname{MEX}$$$ 的总和。更正式地说,运算执行后的值是 $$$\sum_{i=1} ^{n} \operatorname{MEX}(a_i)$$$。
评估所有可能的不同独立操作的值的总和。如果整数的有序三元组 $$$(i,j,k)$$$ 不同,则两个操作是不同的。
$$$\operatorname{MEX}(a)$$$ 被定义为数组中不存在的最小非负整数。例如,$$$\operatorname{MEX}([1, 2, 0, 5])$$$ 为 $$$3$$$,$$$\operatorname{MEX}([1, 2, 4, 9])$$$ 为 $$$0$$$。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 数组的数量。
接下来的 $$$n$$$ 行以 $$$l_i$$$ ($$$1 \le l_i \le 10^5$$$) 开头 - 第 $$$i$$$ 数组的长度 - 然后包含 $$$l_i$$$ 整数 $$$a_1, a_2, \ldots, a_{l_i}$$$ ($$$0 \le a_{i_j} \le 10^6$$$) — 数组 $$$a_i$$$。
保证所有测试用例的 $$$l_i$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出所有可能的不同操作的值的总和。
示例
输入复制
621 02 1 231 12 2 33 4 5 654 1 7 8 102 5 62 0 72 6 62 6 821 33 0 1 226 0 0 1 2 2 33 0 2 3101 09 7 8 0 1 5 6 4 3 28 4 3 8 6 2 5 0 17 2 3 0 1 0 4 02 3 19 2 0 5 4 1 3 0 0 07 6 3 2 4 1 8 05 3 2 4 1 04 0 3 1 13 0 3 2
输出复制
605084319202
注意
对于第一个测试用例,我们有 3 种可能的不同操作:
- $$$i = 1, j = 1, k = 2$$$:数组现在为 [] 和 [$$$0, 1, 2$$$],其 $$$\operatorname{mex}$$$ 分别为 $$$0$$$ 和 $$$3$$$,因此操作的值为 $$$3$$$。
- $$$i = 2, j = 1, k = 1$$$:数组现在为 [$$$0, 1$$$] 和 [$$$2$$$],其 $$$\operatorname{mex}$$$ 分别为 $$$2$$$ 和 $$$0$$$,因此操作的值为 $$$2$$$。
- $$$i = 2, j = 2, k = 1$$$:数组现在为 [$$$0, 2$$$] 和 [$$$1$$$],其 $$$\operatorname{mex}$$$ 分别为 $$$1$$$ 和 $$$0$$$,因此操作的值为 $$$1$$$。
对于第二个测试用例,由于没有数组包含零,因此所有操作的值将为 $$$0$$$。