Move, ant! (pt 2)


Submit solution

Points: 4.5 (partial)
Time limit: 2.0s
JAVA11 4.0s
Python 3 3.0s
Memory limit: 250M
JAVA11 500M
Python 3 500M

Author:
Problem types

Part 1: http://www.laptrinhonline.club/problem/ftwmoveantp1

After randomly picking out obstacles, the ant still couldn't crawl to the last row. Koi wonders what is the smallest amount of obstacles he has to pick so that the ant is able to crawl to the top (last row)?

Input

The first line contains an integer, the number of testcases in the test.

The descriptions of testcases follow.

Each description begins with a line that contains two integer \(n\) \((3 \le n)\) and \(k\) \((1 \le k < (n - 1)^2)\), the size of the table and the number of obstacles Koi picked up, respectively. This is followed by \(k\) lines, each line contains two integers \(r\) and \(c\) \((2 \le r \le n - 1, 1 \le c \le n)\), the position (row, column) of the obstacles.

It is guaranteed that the sum of \(n\) over all input testcases does not exceed \(1000\), and the position of obstacles are different.

Output

For each testcase, output a natural number in one line.

Example

Input:

1
5 3
2 2
3 2
3 3

Output:

1

Explanation: Koi need to pick up 1 more obstacle in row 4 column 2 or row 4 column 3 so that the ant can crawl to the last row.


Comments