Nene 作为篮球教练正在训练她的队伍。Nene 的队伍由 $n$ 名球员组成，编号为 $1$ 到 $n$。第 $i$ 名球员有一个“手臂区间” $[l_i,r_i]$。两名球员 $i$ 和 $j$（$i \neq j$）可以互相传球，当且仅当 $|i-j|\in[l_i+l_j,r_i+r_j]$（这里 $|x|$ 表示 $x$ 的绝对值）。

Nene 想要测试这些球员的配合能力。为此，她将举行若干轮评估。

• 在每一轮中，Nene 将选择一个球员序列 $p_1,p_2,\ldots,p_m$，使得对于所有 $1 \le i < m$，球员 $p_i$ 和 $p_{i+1}$ 都可以互相传球。序列的长度 $m$ 可以由 Nene 决定。每个球员可以在序列 $p_1,p_2,\ldots,p_m$ 中出现多次，也可以完全不出现。
• 然后，Nene 会将球传给球员 $p_1$，球员 $p_1$ 将球传给球员 $p_2$，依此类推……球员 $p_m$ 将球扔出篮球场，使其无法再被使用。

作为教练，Nene 希望 $n$ 名球员中的每一个人都至少在某一轮评估中出现。由于 Nene 放学后要去约会，她希望你计算完成该任务所需的最小评估轮数。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 2\cdot 10^5$）。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2\cdot 10^6$）—— 球员的数量。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1\leq l_i\leq r_i\leq n$）—— 第 $i$ 名球员的手臂区间。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^6$。

输出格式

对于每个测试用例，输出一个整数 —— Nene 完成工作所需的最小评估轮数。

样例

输入 1

5
2
1 1
1 1
2
1 1
2 2
3
1 3
1 3
1 3
5
1 1
2 2
1 5
2 2
1 1
6
1 2
5 5
2 3
2 3
2 2
1 2

输出 1

2
2
2
1
3

说明

在头两个测试用例中，Nene 可以举行两轮评估：一轮使用 $p=[1]$，另一轮使用 $p=[2]$。可以证明举行一轮评估是不够的，因此答案为 $2$。

在第三个测试用例中，Nene 可以举行两轮评估：一轮使用 $p=[1,3]$，另一轮使用 $p=[2]$。球员 $1$ 可以将球传给球员 $3$，因为 $|3-1|=2 \in [1+1,3+3]$。可以证明举行一轮评估是不够的，因此答案为 $2$。