У 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$ не является рекордом, так как её значение равно максимуму из уже встречавшихся.