M. Minimum Records
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 \gt a_j$$$ for every $$$1\le j \lt 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.

Example
Input
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
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.