C. Ладейное поле
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана шахматная доска размера $$$n \times n$$$. Строки и столбцы доски пронумерованы от $$$1$$$ до $$$n$$$. Клетка $$$(x, y)$$$ лежит на пересечении столбца номер $$$x$$$ и строки номер $$$y$$$.

Ладья это шахматная фигура, которая за один ход может переместиться на любое количество клеток по вертикали, либо по горизонтали. На доске размещены $$$m$$$ ладей ($$$m < n$$$), которые не бьют друг друга. То есть, нет пары ладей, стоящих на одной вертикали или горизонтали.

За один ход можно сделать ход одной из ладей. То есть, переместить ее на любое количество клеток по вертикали или горизонтали. При этом, после хода ладья снова не должна оказаться под боем других ладей. Какое минимальное количество ходов нужно сделать, чтобы разместить все ладьи на главной диагонали?

Главной диагональю называются клетки $$$(i, i)$$$, где $$$1 \le i \le n$$$.

Входные данные

В первой строке дано целое число $$$t$$$ — количество тестовых случаев ($$$1 \leq t \leq 10^3$$$). Далее дано описание $$$t$$$ тестовых случаев.

В первой строке даны два целых числа $$$n$$$ и $$$m$$$ — размер поля и количество ладей ($$$2 \leq n \leq 10^5$$$, $$$1 \leq m < n$$$). Следующие $$$m$$$ строк содержат пары целых чисел $$$x_i$$$ и $$$y_i$$$ — позиции ладей, $$$i$$$-я ладья исходно стоит в клетке $$$(x_i, y_i)$$$ ($$$1 \leq x_i, y_i \leq n$$$). Гарантируется, что в исходной расстановке ладьи не бьют друг друга.

Сумма $$$n$$$ по всем тестовым случаям не превышает $$$10^5$$$.

Выходные данные

Для каждого из $$$t$$$ тестовых случаев в новой строке выведите наименьшее количество ходов, которые требуются, чтобы поставить все ладьи на главную диагональ.

Можно доказать, что это всегда возможно.

Пример
Входные данные
4
3 1
2 3
3 2
2 1
1 2
5 3
2 3
3 1
1 2
5 4
4 5
5 1
2 2
3 3
Выходные данные
1
3
4
2
Примечание

Возможные ходы для первых трех тестовых случаев:

  1. $$$(2, 3) \to (2, 2)$$$
  2. $$$(2, 1) \to (2, 3)$$$, $$$(1, 2) \to (1, 1)$$$, $$$(2, 3) \to (2, 2)$$$
  3. $$$(2, 3) \to (2, 4)$$$, $$$(2, 4) \to (4, 4)$$$, $$$(3, 1) \to (3, 3)$$$, $$$(1, 2) \to (1, 1)$$$