桌上放着一副图卡。每张图卡 $\chi$ 上都绘有一个无向简单图 $G_\chi$，使得 $G_\chi$ 是连通的，且 $G_\chi$ 的节点数与边数相等。注意，不同的图卡可能具有不同数量的节点。示例如下：

我们称两张图卡是相同的，当且仅当它们关联的图 $G_1 = (V_1, E_1)$ 和 $G_2 = (V_2, E_2)$ 是同构的；也就是说，存在一个从节点集 $V_1$ 到 $V_2$ 的双射 $f$，使得对于每一对 $x, y \in V_1$，边 $(x, y) \in E_1$ 当且仅当边 $(f(x), f(y)) \in E_2$。我们的目标是计算这副牌中不同图卡的数量。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。对于每个测试用例，给定一副图卡。首先输入一行，包含图卡的数量 $n > 0$。接下来有 $n$ 行，每行代表一张与图 $G$ 关联的图卡，格式如下：

$$k \ u_1 \ v_1 \ u_2 \ v_2 \ \dots \ u_k \ v_k$$

其中 $k > 0$ 表示 $G$ 中的节点数（也是边数），对于每个 $i \in [1, k]$，$(u_i, v_i)$ 表示 $G$ 中连接节点 $u_i$ 和 $v_i$ 的一条边。注意，节点的标识符是 $[1, k]$ 范围内的整数。

输出格式

对于每个测试用例，输出一行，表示给定牌组中不同图卡的数量。

数据范围

• $0 < t \le 30$
• $0 < n, k \le 10^6$
• 对于每个测试用例，$n$ 张图卡中的节点数总和不超过 $10^6$。

样例

输入格式 1

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

输出格式 1

1

输入格式 2

2
2
4 1 2 2 3 3 1 1 4
5 1 2 2 3 3 1 2 4 2 5
3
9 1 2 2 5 5 7 7 6 6 3 3 1 2 4 7 9 9 8
9 1 4 4 2 2 3 3 5 5 7 7 6 6 4 7 8 8 9
9 1 2 2 5 5 4 4 1 4 7 7 8 8 6 8 9 5 3

输出格式 2

2
2