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$를 기록 위치(record position)라고 부릅니다. 특히, 위치 $1$은 항상 기록 위치입니다.

VegiCat이 기록 위치의 개수를 최소화할 수 있도록 도와주십시오. 이 최솟값을 출력하십시오.

입력

첫 번째 줄에는 테스트 케이스의 개수인 정수 $T$ ($1 \le T \le 10^4$)가 주어집니다. 이어서 테스트 케이스의 설명이 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 구간의 개수인 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다.

다음 $n$개의 줄 중 $i$번째 줄에는 위치 $i$에서 선택할 수 있는 구간을 나타내는 두 정수 $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$)가 주어집니다.

모든 테스트 케이스에서 $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$은 그 값이 지금까지 나온 최댓값과 같기 때문에 기록 위치가 아닙니다.