Problem Description

Consider a 2 × n grid graph with nodes (x, y) where x ∈ {0, 1} and y ∈ {1, 2, · · · , n}. The initial graph has 3n - 2 edges connecting all pairs of adjacent nodes.
You need to maintain the graph with two types of different adjustments. The first one, denoted by “1 $x_0$ $y_0$ $x_1$ $y_1$”,adds an new edge between the nodes ($x_0, y_0$) and ($x_1, y_1$) which was not exist. The second one, denoted by“2 $x_0$ $y_0$ $x_1$ $y_1$”, erases an existed edge between the nodes ($x_0, y_0$) and ($x_1, y_1$).
It is sure that, for each adjustment, ($x_0, y_0$) and ($x_1, y_1$) were adjacent in the original grid graph. That is say thateither they share the same x coordinate and |$y_0 - y_1$| = 1, or they share the same y coordinate and |$x_0 - x_1$| = 1.
After each adjustment, we guarantee the connectedness of the graph and you need to calculate the number of bridges in the current graph.

Input

The first line of input contains an integer T (1 ≤ T ≤ 1001) which is the total number of test cases. For each test case, the first line contains integers n (1 ≤ n ≤ 200000) and m (0 ≤ m ≤ 200000); n indicates the size of the graph
and m is the number of adjustments. Each of the following m lines contains an adjustment described as above.
Only one case satisfies n + m ≥ 2000.

Output

For each test case, output m lines, each of which contains the number of bridges.

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

0
0
7
4
2
4
2
4
1
2