C. Rooks
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have an $$$n \times n$$$ chessboard and $$$k$$$ rooks. Rows of this chessboard are numbered by integers from $$$1$$$ to $$$n$$$ from top to bottom and columns of this chessboard are numbered by integers from $$$1$$$ to $$$n$$$ from left to right. The cell $$$(x,y)$$$ is the cell on the intersection of row $$$x$$$ and column $$$y$$$ for $$$1 \le x \le n$$$ an $$$1 \le y \le n$$$.

A rook attacks all cells that are in its row or column.

You have to remove some rooks from the board such that there is at least one empty cell which is not attacked by any rook.

What is the minimum number of rooks you have to remove ?

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 100)$$$ — the number of test cases.

The first line of each test case contains two integers $$$n$$$ $$$(1 \le n \le 50)$$$ the size of the chessboard and $$$k$$$ $$$(0 \le k \le n^2)$$$ the number of rooks.

Each of the next $$$k$$$ lines of each test case contains two integers $$$x$$$ and $$$y$$$ $$$(1 \le x,y \le n)$$$ — there is a rook in cell $$$(x,y)$$$

Output

For each test case, output one integer $$$m$$$ $$$(0 \le m \le k)$$$, the minimum number of rooks to remove.

Example
Input
1
4 6
1 2
1 4
2 1
3 3
4 2
4 4
Output
1
Note

Consider example. The board will look like the following picture. You have to remove the rook colored in red in order to obtain a square which is not attacked by any rook.