考虑一个 $2 \times n$ 的网格图，其节点为 $(x, y)$，其中 $x \in \{0, 1\}$ 且 $y \in \{1, 2, \dots, n\}$。初始图有 $3n - 2$ 条边，连接所有相邻的节点。

你需要维护该图，并进行两种不同类型的调整。第一种调整记为 “1 $x_0$ $y_0$ $x_1$ $y_1$”，表示在节点 $(x_0, y_0)$ 和 $(x_1, y_1)$ 之间添加一条原本不存在的新边。第二种调整记为 “2 $x_0$ $y_0$ $x_1$ $y_1$”，表示删除节点 $(x_0, y_0)$ 和 $(x_1, y_1)$ 之间已存在的一条边。

题目保证对于每次调整，$(x_0, y_0)$ 和 $(x_1, y_1)$ 在原始网格图中是相邻的。也就是说，它们要么具有相同的 $x$ 坐标且 $|y_0 - y_1| = 1$，要么具有相同的 $y$ 坐标且 $|x_0 - x_1| = 1$。

在每次调整后，我们保证图的连通性，你需要计算当前图中桥的数量。

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 1001$)，表示测试用例的总数。对于每个测试用例，第一行包含整数 $n$ ($1 \le n \le 200000$) 和 $m$ ($0 \le m \le 200000$)；$n$ 表示图的大小，$m$ 表示调整的次数。接下来的 $m$ 行，每行包含上述的一种调整。

只有一个测试用例满足 $n + m \ge 2000$。

输出格式

对于每个测试用例，输出 $m$ 行，每行包含当前图中桥的数量。

样例

样例输入 1

2
4 8
2 0 3 1 3
2 0 2 1 2
2 0 4 1 4
1 0 2 1 2
1 0 3 1 3
2 0 1 1 1
1 0 4 1 4
2 1 2 1 3
6 2
2 1 2 1 3
2 0 4 0 5

样例输出 1

0
0
7
4
2
4
2
4
1
2