VegiCat は $n$ 個の整数の閉区間 $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$ を持っています。

彼は各区間 $[l_i, r_i]$ から整数 $a_i$ を 1 つずつ選ぶことで、数列 $a_1, a_2, \ldots, a_n$ を構築したいと考えています。つまり、すべての $1 \le i \le n$ に対して $l_i \le a_i \le r_i$ です。

すべての $1 \le j < i$ に対して $a_i > a_j$ が成り立つとき、位置 $i$ を記録位置（record position）と呼びます。特に、位置 $1$ は常に記録位置です。

VegiCat が記録位置の個数を最小化するのを手伝ってください。この最小値を出力してください。

入力

最初の行には、テストケースの数を表す整数 $T$（$1 \le T \le 10^4$）が含まれます。続いて各テストケースの説明が与えられます。

各テストケースの 1 行目には、区間の個数を表す整数 $n$（$1 \le n \le 10^6$）が含まれます。

続く $n$ 行のうち $i$ 行目には、位置 $i$ で利用可能な区間を表す 2 つの整数 $l_i, r_i$（$-10^9 \le l_i \le r_i \le 10^9$）が含まれます。

すべてのテストケースにおける $n$ の総和は $10^6$ を超えないことが保証されています。

出力

各テストケースについて、記録位置の個数の最小値を表す整数を 1 つ出力してください。

入出力例

入力 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

注記

1 つ目のテストケースでは、最適な数列の 1 つは $a = [1, 100, 20, 30]$ です。その記録位置は $1$ と $2$ です。

2 つ目のテストケースでは、最適な数列の 1 つは $a = [-1, 4, 1, 2, 8, 6, 12, 12]$ です。その記録位置は $1, 2, 5$ および $7$ です。位置 $8$ は、その値がそれまでに出現した最大値と等しいため、記録位置ではありません。