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$ 不是纪录位置，因为它的值等于目前为止出现过的最大值。