有 对夫妇,一开始夫妇之间互不认识,若两男或两女成为朋友，称他们为“熟人”，“熟人”关系具有传递性，即若 熟 且 熟 则 熟 。若两组夫妇的丈夫互相为熟人且妻子也相互为熟人则称他们为“熟悉的一对”。
现在给出 个事件，每个事件会使得两男或两女成为朋友，并在每次事件之后计算“熟悉的一对”的个数。
第一行一个数 ，表示数据组数。
接下来一行两个整数 表示对数和事件数。
接下来 行，每行三个整数 ，若 ，表示男 和男 成为朋友，，表示女 和女 成为朋友。
设当前是第 个操作， 为本次事件之后的答案，令 ，请输出 模 之后的值。
1 3 5 1 1 2 2 1 3 1 2 3 1 3 1 2 2 1
22
对于 的数据，，。
