Djangle gives you a connected simple undirected graph, where each edge is initially colored either white or black.

In each operation, you can choose a simple cycle that contains at least one white edge and color all edges in this cycle black. Note that you do not necessarily need to make all edges in the graph black at the end.

What is the maximum number of such operations you can perform?

A simple cycle is defined as a closed path formed by connecting several edges end-to-end, without repeating any edges.

Input

The first line contains an integer $T(1 \le T \le 10^4)$, representing the number of test cases.

The first line of each test case contains two integers $n, m(1 \le n \le \sum n \le 2 \times 10^5, n-1 \le m \le \min\{3 \times 10^5, \frac{n(n-1)}{2}\}, \sum m \le 3 \times 10^5)$, representing the number of vertices and edges in the graph.

The next $m$ lines each contain three integers $u, v, \text{col}(1 \le u, v \le n, \text{col} \in \{0, 1\})$, representing an undirected edge connecting vertex $u$ and vertex $v$ with color $\text{col}$. If $\text{col} = 0$, the edge is white; otherwise, it is black.

It is guaranteed that the input graph contains no multiple edges or self-loops.

Output

For each test case, output a single integer representing the maximum number of operations that can be performed.

Examples

Input 1

1
9 10
1 2 1
2 3 0
3 4 1
4 5 0
5 6 1
6 7 0
7 8 1
8 1 0
2 9 0
9 6 1

Output 1

2

Note

The first operation is the simple cycle $2 - 9 - 6 - 7 - 8 - 1 - 2$, and the second operation is the simple cycle $1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 1$.

It is easy to prove that there is no other operation scheme that allows for more than 2 operations.