SP131 SQDANCE - Square dance

你被法国国家安全局（NSA）雇佣，目的是破解 Pink Card 上使用的 RSA 密码。最简单的方法是分解公钥模数，你已经找到了最快的算法，但需要解决一个子问题，该问题可以建模如下： 设 $ \mathcal{P} = \{p_1, p_2, \dots, p_n\} $ 是一组质数。 我们称一对**关系**为一对质数 $(p,q)$，其中 $ p $ 和 $ q $ 是 $ \mathcal{P} $ 中不同的元素。给定 $ R $ 个关系 $ S_i = \{p_i, q_i\} $。 依次插入关系 $S_i$，同时你需要动态维护一个集合 $C=\{S_{j_1},S_{j_2},\cdots,S_{j_k}\}$（初始时 $C$ 是空集）。现在处理 $S_i$：如果存在一个 $C$ 的子集 $D=\{S_{t_1},S_{t_2},\cdots,S_{t_r}\}$，使得 $p_{t_1}\times p_{t_2}\times \cdots\times p_{t_r}\cdots q_{t_1}\times q_{t_2}\times \cdots \times q_{t_r}$ 是一个 **完全平方数**，则增加平方数的计数，但不把 $S_i$ 加入 $C$。否则，把 $S_i$ 加入 $C$。 你需要统计过程中出现的平方数数量。

输入的第一行包含一个数字 $ T $，表示测试用例的数量。 每个测试用例的第一行包含两个整数 $ P $ 和 $ R $： - $ P$ 是该测试用例中出现的质数的数量； - $ R$ 是到达的质数集合的数量。 随后的 $ R $ 行，每行包含两个整数 $ i $ 和 $ j $，构成一个集合 $ \\{p_i, p_j\\} $（$ 1 \leq i, j \leq P $）。

对每组数据，输出一行，表示统计过程中出现的平方数数量。 多组数据之间以换行符隔开。

### 样例 1 解释 首先到达 $ S_1 = \{2, 3\} $，我们把它放入 $ C $； 然后到达 $ S_2 = \{5, 11\} $、$ S_3 = \{3, 7\} $，它们也被存入 $ C} $。 现在进入关系 $ S_4 = \{2, 7\} $。这个关系可以用来形成平方：$ S_1 * S_3 * S_4 = (2\times 3) \times (3 \times 7) \times (2 \times 7) = (2 \times 3\times 7)^2 $ 所以我们计数，并且不将 $ S_4 $ 存入 $ C $。 现在我们考虑 $ S_5 = \{5, 11\} $，它可以与 $ S_2 $ 形成一个平方，所以再计数。 然后 $ S_6 = \{2, 13\} $ 被放入 $ C$。 现在 $ S_7 = \{7, 13\} $，发现$ S_1 * S_3 * S_6 * S_7 $ 可以形成平方，于是计数。 最终，我们得到 $3$ 个平方。 ### 数据范围 对于所有数据，$1\le T\le 30$，$1\le P,R\le 10^5$。