Given a graph of N vertices, numbered from 0 to N - 1. Initially, there is no edge in the graph. Sequentially adding M undirected edges (u, v) to the graph (0 <= u, v <= N - 1). After adding an edge, you must print out the current number of bridges in the graph. The data guarantees that there is no request to add an existed edge, or an edge from a vertex to itself.

Input

The first line contains an integer T (T <= 10) denotes the number of test cases. Each test case begins with 2 integers N (1 <= N <= 50000) and M (1 <= M <= 100000), followed by M lines, each line contains a pair of integers (u, v) represents a request to add an edge (u, v) to the graph.

Output

After each request, print out the current number of bridges in the graph on a separate line.

Example

For the input data:

1
5 10
3 0
0 2
1 0
1 3
1 4
2 4
4 0
2 1
2 3
3 4

the correct result is:

1
2
3
1
2
0
0
0
0
0