A. Marble's Birthday
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Nagham loves graphs, so she came up with this idea at 12a.m. But sadly, she didn't know how to solve it. Luckily for her, Ahmad, although he is a bully, saw Marble on that day and was happy, so he decided to be a goody guy and solve it for her.

Marble
You are given $$$n$$$ nodes and $$$m$$$ edges, and your task is to determine the minimum number of edges you need to add such that after the additions, every node will be able to reach every other node.
Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) – the number of test cases.

The first line of each test contains $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5$$$) ($$$1 \leq m \leq 5 \cdot 10^5$$$).

The next $$$m$$$ lines of each test contain integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$) – meaning there is a directed edge from $$$u$$$ to $$$v$$$.

It's guaranteed that the sum of $$$n$$$ and $$$m$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For each test case, output the minimum number of edges to make the graph connected.

Example
Input
1
4 5
1 2
2 3
3 1
1 4
3 4
Output
1