VegiCat has $n$ closed integer intervals $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$.

He wants to construct a sequence $a_1, a_2, \ldots, a_n$ by choosing an integer $a_i$ from each interval $[l_i, r_i]$. That is, $l_i \le a_i \le r_i$ for every $1 \le i \le n$.

A position $i$ is called a record position if $a_i > a_j$ for every $1 \le j < i$. In particular, position $1$ is always a record position.

Help VegiCat minimize the number of record positions. Output this minimum number.

Input

The first line contains an integer $T$ ($1 \le T \le 10^4$), the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 10^6$), the number of intervals.

The $i$-th of the next $n$ lines contains two integers $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$), describing the interval available at position $i$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output an integer — the minimum possible number of record positions.

Examples

Input 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

Output 1

2
4

Note

In the first test case, one optimal sequence is $a = [1, 100, 20, 30]$. Its record positions are $1$ and $2$.

In the second test case, one optimal sequence is $a = [-1, 4, 1, 2, 8, 6, 12, 12]$. Its record positions are $1, 2, 5$, and $7$. Position $8$ is not a record because its value equals the maximum seen so far.