Дана шахматная доска размера \(n \times n\). Строки и столбцы доски пронумерованы от \(1\) до \(n\). Клетка \((x, y)\) лежит на пересечении столбца номер \(x\) и строки номер \(y\).
Ладья это шахматная фигура, которая за один ход может переместиться на любое количество клеток по вертикали, либо по горизонтали. На доске размещены \(m\) ладей (\(m < n\)), которые не бьют друг друга. То есть, нет пары ладей, стоящих на одной вертикали или горизонтали.
За один ход можно сделать ход одной из ладей. То есть, переместить ее на любое количество клеток по вертикали или горизонтали. При этом, после хода ладья снова не должна оказаться под боем других ладей. Какое минимальное количество ходов нужно сделать, чтобы разместить все ладьи на главной диагонали?
Главной диагональю называются клетки \((i, i)\), где \(1 \le i \le n\).
Выходные данные
Для каждого из \(t\) тестовых случаев в новой строке выведите наименьшее количество ходов, которые требуются, чтобы поставить все ладьи на главную диагональ.
Можно доказать, что это всегда возможно.
Примечание
Возможные ходы для первых трех тестовых случаев:
- \((2, 3) \to (2, 2)\)
- \((2, 1) \to (2, 3)\), \((1, 2) \to (1, 1)\), \((2, 3) \to (2, 2)\)
- \((2, 3) \to (2, 4)\), \((2, 4) \to (4, 4)\), \((3, 1) \to (3, 3)\), \((1, 2) \to (1, 1)\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|