Vitya 有一个朋友 Masha,他非常想邀请她来参加他最喜欢的乐队表演的音乐节。然而,为了让朋友同意,她必须首先评估发布的新奇事物。 Vitya 知道,如果 Masha 听的歌曲比之前所有的歌曲都酷,她将获得 1 个单位的印象。不幸的是,专辑只能完整收听,而不能在某些地方更改其中的歌曲。
帮助Vitya找到这样的专辑顺序,以便玛莎的印象尽可能地好,她一定会和他一起去音乐节。
输入
每个测试由多个测试用例组成。第一行包含一个整数 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$$$。
输出
对于每个测试用例,打印单数——玛莎可以获得的最大印象。
示例
输入 #1
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
输出 #1
4 4
注意
在第一个测试示例中,最佳顺序是收听第四张、第二张、第三张和第一张专辑。
在这种情况下,玛莎将按以下顺序收听曲目:1; 7; 8、6; 4、9、4、6、8 将获得 4 个展示单位。
在第二个测试示例中,您必须首先听第一个,然后是第四个,然后以任意顺序听第二个和第三个。 在这种情况下,玛莎将获得最大的印象,并且对于第一张和第四张专辑中的每首歌来说,第二张和第三张专辑中没有任何歌曲。