Sanggeun's travels

Sanggeun decided to spend the winter break traveling through $N$ countries and finding himself. He is scared of planes he has never been on, so he wants to ride as few kinds of planes as possible while moving between countries.

Given the flight schedule for this break, find the smallest number of plane kinds Sanggeun needs in order to visit every country.

On the way from one country to another he may pass through other countries, including ones he has already visited.

The first line contains the number of test cases $T$. ($T \le 100$)

Each test case is given as follows.

• The first line contains the number of countries $N$ and the number of plane kinds $M$. ($2 \le N \le 1000$, $1 \le M \le 10000$)
• Each of the next $M$ lines contains two integers $a$ and $b$, meaning there is a plane that flies back and forth between $a$ and $b$. ($1 \le a, b \le N$, $a \ne b$)

The given flight schedule always forms a connected graph.

For each test case, print on one line the minimum number of plane kinds Sanggeun has to ride to travel to every country.