Nene는 농구 코치로서 팀을 훈련시키고 있습니다. Nene의 팀은 $1$부터 $n$까지 번호가 매겨진 $n$명의 선수로 구성되어 있습니다. $i$번째 선수는 팔 구간(arm interval) $[l_i, r_i]$를 가집니다. 두 선수 $i$와 $j$ ($i \neq j$)는 $|i-j| \in [l_i+l_j, r_i+r_j]$일 때만 서로 공을 패스할 수 있습니다 (여기서 $|x|$는 $x$의 절댓값을 의미합니다).

Nene는 선수들의 협동 능력을 테스트하려고 합니다. 이를 위해 그녀는 여러 번의 평가 라운드를 진행할 것입니다.

• 각 라운드에서 Nene는 모든 $1 \le i < m$에 대해 선수 $p_i$와 $p_{i+1}$이 서로 공을 패스할 수 있는 선수들의 수열 $p_1, p_2, \ldots, p_m$을 선택합니다. 수열의 길이 $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$번째 줄에는 $i$번째 선수의 팔 구간인 두 정수 $l_i$와 $r_i$ ($1\leq l_i\leq r_i\leq n$)가 주어집니다.

모든 테스트 케이스에 대한 $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]$인 라운드 하나, 총 두 번의 평가 라운드를 진행할 수 있습니다. $|3-1|=2 \in [1+1, 3+3]$이므로 선수 $1$은 선수 $3$에게 공을 패스할 수 있습니다. 한 번의 평가 라운드만으로는 충분하지 않음이 증명될 수 있으므로 정답은 $2$입니다.