Little Y is visiting a park. The map of this park can be represented by an undirected simple connected graph containing $n$ nodes and $m$ edges. To help travelers plan their routes, there are several cycles in the map; each cycle can be represented by a sequence of distinct nodes $e_1, e_2, \dots, e_l$, where $l \ge 3$, and for all $1 \le i \le l$, there exists an edge in the graph connecting $e_i$ and $e_{(i \bmod l)+1}$. Additionally, the set of edges connecting all nodes in order on the cycle is called the edge set of the cycle, and two cycles are considered different if and only if their edge sets are different. As Little Y continued the visit, he discovered a property: each edge in the graph appears in at most one cycle.

Currently, there is no lighting system in the park, so when night falls, the park will be completely dark. Fortunately, the staff is preparing to place lighthouses at some nodes on the map. The distance between two nodes on the graph is defined as the minimum number of edges that must be traversed to reach one node from another. Therefore, each lighthouse, in addition to illuminating its placement node, can also illuminate all nodes that are at a distance of no more than $k$ from the placement node.

As a competitive programming contestant, Little Y naturally thought of a question: what is the minimum number of lighthouses that need to be placed to ensure that all nodes are illuminated?

Input

This problem contains multiple test cases. The first line of input contains an integer $T$ ($1 \le T \le 10^5$), representing the number of test cases.

For each test case:

The first line contains three integers $n, m, k$ ($2 \le n \le 2 \times 10^5$, $n-1 \le m \le 2 \times 10^5$, $1 \le k \le n$), representing the number of nodes and edges on the map, as well as the maximum distance that a lighthouse can illuminate.

The next $m$ lines each contain two integers $u, v$ ($1 \le u, v \le n, u \ne v$), representing an edge on the map.

It is guaranteed that the given undirected graph is connected and has no multiple edges or self-loops, and each edge appears in at most one cycle. Additionally, the total sum of $n$ and $m$ across all test cases does not exceed $2 \times 10^5$.

Output

For each test case, output a single integer representing the minimum number of lighthouses that need to be placed.

Example

Input

3
5 4 1
1 2
1 3
3 4
1 5
5 5 1
1 2
2 3
3 4
4 5
5 1
8 8 2
1 2
2 3
3 4
4 5
5 1
1 6
2 7
3 8

Output

2
2
1

Note

For the first test case, two lighthouses can be placed at node 1 and node 4 respectively.

For the second test case, two lighthouses can be placed at node 2 and node 5 respectively.

For the third test case, one feasible solution is to place a lighthouse at node 2. It can be proven that this is the only solution that satisfies the condition of having the minimum number of lighthouses.