G. Смешивание MEXов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n$$$ массивов $$$a_1, a_2, \ldots, a_n$$$.

Следующая операция выполняется ровно один раз:

  • Выберите любой массив из $$$a_1, a_2, \ldots, a_n$$$. Предположим, вы выбрали массив $$$a_i$$$ ($$$1 \leq i \leq n$$$).
  • Выберите любой элемент в массиве $$$a_i$$$. Предположим, вы выбрали $$$j$$$-й элемент массива $$$a_i$$$, обозначенный как $$$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,j}$$$ из $$$a_i$$$.
  • Значение этой операции $$$(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$$$.

Выходные данные

Для каждого набора входных данных выведите сумму значений всех возможных различных операций.

Пример
Входные данные
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 возможные различные операции:

  • $$$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$$$.