在 CCPC 哈尔滨站 2019 的彩排结束后，仍有 $m$ 名参赛选手留在赛场。他们正在拍照、讨论题目并交换礼物。

最初，每个人手中恰好有一个礼物。注意，一些选手可能持有相同类型的礼物。具体来说，第 $i$ 位选手手中礼物的类型可以用一个正整数 $g_i$ 表示。两位选手 $i$ 和 $j$ ($1 \le i, j \le m$) 持有相同类型的礼物，当且仅当 $g_i = g_j$。

这 $m$ 名选手之间可以进行多轮礼物交换。在每一轮中，两名选手可以互相交换手中的礼物。注意，一对选手如果愿意，可以多次交换礼物。最终，每位选手手中仍将恰好有一个礼物。

令 $h_i$ 表示最终第 $i$ 位选手手中礼物的类型。如果 $g_i \neq h_i$，则第 $i$ 位选手会感到高兴，因为他们得到了与初始时不同类型的礼物；否则他们会不高兴。你的任务是编写一个程序，帮助他们交换礼物，使得高兴的选手人数最大化。例如，如果 $g = [3, 3, 2, 1, 3]$ 且 $h = [1, 2, 3, 3, 3]$，则会有 4 位选手感到高兴。

由于 $m$ 可能非常大，你将得到 $n$ 个序列 $s_1, s_2, \dots, s_n$，且序列 $g$ 等于 $s_n$。第 $i$ ($1 \le i \le n$) 个序列将以以下两种格式之一给出：

• “1 k q[1..k]” ($1 \le k \le 10^6, 1 \le q_i \le 10^9$)：表示 $s_i = [q_1, q_2, \dots, q_k]$。
• “2 x y” ($1 \le x, y \le i - 1$)：表示 $s_i = s_x + s_y$。这里“+”表示序列的拼接，例如 $[3, 3, 2] + [2, 2, 3, 3] = [3, 3, 2, 2, 2, 3, 3]$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10\,000$)，表示测试数据的组数。

对于每组数据，第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示序列的数量。接下来的 $n$ 行，每行描述一个序列，格式如题目所述，其中第 $i$ ($1 \le i \le n$) 行描述序列 $s_i$。

保证所有测试数据的 $n$ 之和不超过 $10^6$，且所有测试数据的 $k$ 之和不超过 $10^6$。同时保证没有任何序列的长度超过 $10^{18}$。

输出格式

对于每组数据，输出一行，包含一个整数，表示高兴的选手的最大人数。

样例

输入 1

2
1
1 5 3 3 2 1 3
3
1 3 3 3 2
1 4 2 2 3 3
2 1 2

输出 1

4
6