F. Нина и игра в баскетбол
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Нина тренирует свою команду по баскетболу. Команда Нины состоит из $$$n$$$ игроков, пронумерованных от $$$1$$$ до $$$n$$$. У $$$i$$$-го игрока есть интервал рук $$$[l_i,r_i]$$$. Два игрока $$$i$$$ и $$$j$$$ ($$$i \neq j$$$) могут передавать мяч друг другу, только если $$$|i-j|\in[l_i+l_j,r_i+r_j]$$$ (здесь $$$|x|$$$ обозначает абсолютное значение $$$x$$$).

Нина хочет проверить готовность своей команды. Для этого она проведет несколько раундов передач.

  • В каждом раунде Нина выберет последовательность игроков $$$p_1,p_2,\ldots,p_m$$$ такую, что игроки $$$p_i$$$ и $$$p_{i+1}$$$ могут передавать мяч друг другу для всех $$$1 \le i < m$$$. Длина последовательности $$$m$$$ может быть выбрана Ниной. Каждый игрок может появиться в последовательности $$$p_1,p_2,\ldots,p_m$$$ несколько раз или вообще не появиться в ней.
  • Затем Нина бросит мяч игроку $$$p_1$$$, игрок $$$p_1$$$ передаст мяч игроку $$$p_2$$$ и так далее... Игрок $$$p_m$$$ выбросит мяч за пределы баскетбольного поля, так что его больше нельзя будет использовать.

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

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

В первой строке дано одно целое число $$$t$$$ ($$$1 \le t \le 2\cdot 10^5$$$) — количество наборов входных данных.

В первой строке дано одно целое число $$$n$$$ ($$$1 \le n \le 2\cdot 10^6$$$) — количество игроков.

В $$$i$$$-й из следующих $$$n$$$ строк даны два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1\leq l_i\leq r_i\leq n$$$) — интервал рук $$$i$$$-го игрока.

Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превосходит $$$2\cdot 10^6$$$.

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

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

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

В первых двух наборах входных данных Нина может провести два раунда передач: один с $$$p=[1]$$$ и один с $$$p=[2]$$$. Можно показать, что одного раунда передач недостаточно, поэтому ответ $$$2$$$.

В третьем наборе входных данных Нина может провести два раунда передач: один с $$$p=[1,3]$$$ и один с $$$p=[2]$$$. Игрок $$$1$$$ может передать мяч игроку $$$3$$$, так как $$$|3-1|=2 \in [1+1,3+3]$$$. Можно показать, что одного раунда передач недостаточно, поэтому ответ $$$2$$$.