Нене тренирует свою команду в качестве баскетбольного тренера. Команда Нене состоит из $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$.

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

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

Примеры

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

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

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

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$.