Neneはバスケットボールのコーチとしてチームを指導している。Neneのチームは $1$ から $n$ までの番号が振られた $n$ 人の選手で構成されている。$i$ 番目の選手は「腕の区間」 $[l_i, r_i]$ を持っている。2人の選手 $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$ 人の選手全員が少なくとも1回の評価ラウンドに登場するようにしたいと考えている。放課後にデートの予定があるため、Neneはタスクを完了するために必要な最小の評価ラウンド数を計算してほしいと頼んできた。

入力

各テストケースには複数のテストケースが含まれる。最初の行にはテストケースの数 $t$ ($1 \le t \le 2\cdot 10^5$) が含まれる。各テストケースの説明が続く。

各テストケースの最初の行には、選手数 $n$ ($1 \le n \le 2\cdot 10^6$) が含まれる。

続く $n$ 行の各行には、$i$ 番目の選手の腕の区間を表す2つの整数 $l_i$ と $r_i$ ($1\leq l_i\leq r_i\leq n$) が含まれる。

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

出力

各テストケースについて、Neneが作業を完了するために必要な最小の評価ラウンド数を1つの整数で出力せよ。

入出力例

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

注記

最初の2つのテストケースでは、Neneは $p=[1]$ と $p=[2]$ という2つの評価ラウンドを行うことができる。1回の評価ラウンドでは不十分であることが示せるため、答えは $2$ となる。

3番目のテストケースでは、Neneは $p=[1,3]$ と $p=[2]$ という2つの評価ラウンドを行うことができる。選手 $1$ は選手 $3$ にパスを出すことができる。なぜなら $|3-1|=2 \in [1+1, 3+3]$ だからである。1回の評価ラウンドでは不十分であることが示せるため、答えは $2$ となる。