C. Музыкальный фестиваль
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Мальчик Витя очень любит слушать музыку. Он пристально следит за обновлениями своих любимых групп, поэтому знает, что в эту пятницу должны быть выпущены $$$n$$$ альбомов, $$$i$$$-й из которых содержит $$$k_i$$$ треков. Разумеется, Витя, как самый преданный фанат, уже послушал все треки, которые должны выйти в ближайшее время, и знает, что в $$$i$$$-м альбоме крутость $$$j$$$-го трека равна $$$a_{i,j}$$$.

У Вити есть подруга Маша, которую он очень хочет пригласить на фестиваль, где выступают его любимые группы. Однако для того, чтобы подруга согласилась, она должна сначала оценить вышедшие новинки. Витя знает, что, если Маша послушает трек, который был круче всех прошлых, она получит 1 единицу впечатления. К сожалению, альбомы можно слушать только целиком, не меняя песни в них местами.

Помогите Вите найти такой порядок альбомов, чтобы впечатление Маши оказалось как можно больше, и она точно сходила вместе с ним на фестиваль.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t ($$$1 \le t \le 200\,000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора дано единственное целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — количество альбомов.

Далее следуют описания альбомов. Каждое описание альбома состоит из двух строк:

В первой строке дано единственное целое число $$$k_i$$$ ($$$1 \le k_i \le 200\,000$$$) — количество треков в $$$i$$$-м альбоме.

В следующей строке даны $$$k_i$$$ целых чисел $$$a_{i, 1},\ a_{i, 2},\ a_{i, 3},\ \ldots,\ a_{i, k_i}$$$ ($$$1 \le a_{i,j} \le 200\,000$$$) — крутость треков в $$$i$$$-м альбоме.

Обозначим за $$$\sum k_i$$$ сумму по всем $$$k_i$$$. Гарантируется, что $$$\sum k_i \le 200\,000$$$.

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

Для каждого тестового набора выведите единственное число — максимальное впечатление, которое может может получить Маша.

Пример

Входные данные
2
4
5
4 9 4 6 8
1
7
2
8 6
1
1
4
2
3 4
2
1 8
2
2 8
2
7 9
Выходные данные
4
4
Примечание

В первом тестовом примере оптимальным порядком является прослушивание 4-го, 2-го, 3-го и 1-го альбомов. В таком случае Маша послушает треки в следующем порядке: 1; 7; 8, 6; 4, 9, 4, 6, 8 и получит 4 единицы впечатления. Во втором тестовом примере необходимо сначала прослушать 1-й, потом 4-й и в любом порядке 2-й и 3-й. В таком случае Маша получит максимальное впечатление, причём за каждую песню в 1-м и 4-м альбомах и ничего за 2-й и 3-й.