VegiCat 有 $n$ 個整數閉區間 $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$。

他希望從每個區間 $[l_i, r_i]$ 中各選擇一個整數 $a_i$ 來構造一個序列 $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$ 為一個紀錄位置。特別地，位置 $1$ 永遠是一個紀錄位置。

請幫助 VegiCat 最小化紀錄位置的數量。輸出此最小數量。

輸入格式

第一行包含一個整數 $T$（$1 \le T \le 10^4$），代表測試資料組數。接下來是各組測試資料的描述。

每組測試資料的第一行包含一個整數 $n$（$1 \le n \le 10^6$），代表區間的數量。

接下來 $n$ 行中的第 $i$ 行包含兩個整數 $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$ 不是紀錄位置，因為它的值等於目前為止見過的最大值。