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 \le l_i \le r_i \le 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$。