У VegiCat є $n$ замкнених цілочисельних відрізків $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$.

Він хоче побудувати послідовність $a_1, a_2, \ldots, a_n$, вибравши по одному цілому числу $a_i$ з кожного відрізка $[l_i, r_i]$. Тобто $l_i \le a_i \le r_i$ для кожного $1 \le i \le n$.

Позиція $i$ називається рекордною позицією, якщо $a_i > a_j$ для кожного $1 \le j < i$. Зокрема, позиція $1$ завжди є рекордною позицією.

Допоможіть VegiCat мінімізувати кількість рекордних позицій. Виведіть цю мінімальну кількість.

Вхідні дані

Перший рядок містить ціле число $T$ ($1 \le T \le 10^4$) — кількість наборів вхідних даних. Далі йде опис наборів вхідних даних.

Перший рядок кожного набору вхідних даних містить ціле число $n$ ($1 \le n \le 10^6$) — кількість відрізків.

$i$-й із наступних $n$ рядків містить два цілі числа $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$), що описують відрізок, доступний на позиції $i$.

Гарантується, що сума $n$ за всіма наборами вхідних даних не перевищує $10^6$.

Вихідні дані

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

Приклади

Вхідні дані 1

2
4
1 1
1 100
20 20
30 30
8
-3 -1
-5 4
0 1
2 2
1 8
5 6
10 12
12 12

Вихідні дані 1

2
4

Примітка

У першому наборі вхідних даних однією з оптимальних послідовностей є $a = [1, 100, 20, 30]$. Її рекордні позиції — $1$ та $2$.

У другому наборі вхідних даних однією з оптимальних послідовностей є $a = [-1, 4, 1, 2, 8, 6, 12, 12]$. Її рекордні позиції — $1, 2, 5$ та $7$. Позиція $8$ не є рекордом, оскільки її значення дорівнює максимуму серед уже бачених.