랩탑

랩탑(노트북)은 들고 다니면서 쓰는 개인용 컴퓨터로, 가장 큰 장점은 휴대성이다. 랩탑은 배터리로 동작하기 때문에 에너지를 아껴 쓰는 것이 중요하다.

랩탑을 일정 시간 동안 사용하지 않으면 에너지를 아끼기 위해 대기 모드나 절전 모드로 들어간다. 이 모드에서는 에너지를 전혀 쓰지 않지만, 다시 켜서 사용하려면 단위 시간당 일정한 양의 에너지를 새로 들여야 한다. 즉 절전 모드에 들어갔다가 다시 켜는 일이 잦을수록 낭비가 커진다. 그래서 전체 에너지 소비를 줄이려면 사용하지 않는(idle) 구간의 개수를 줄여야 한다.

여러 개의 작업 $T_1, T_2, \dots, T_n$ 을 이 랩탑 하나로 처리하려고 한다. 각 작업 $T_i$ 는 릴리즈 시간 $r_i$ 와 데드라인 $d_i$ 를 가진다. 각 작업은 정확히 단위 시간(1)만큼 실행되며, 정수 시각에 시작해서 구간 $[r_i, d_i]$ 안에서 시작하고 끝나야 한다. 즉 작업 $T_i$ 를 정수 시각 $t$ 에 실행하면 $[t, t+1]$ 구간을 차지하고, $r_i \le t$ 와 $t + 1 \le d_i$ 를 만족해야 한다. 한 시각에는 하나의 작업만 실행할 수 있으므로 두 작업이 같은 단위 구간을 차지할 수 없다.

작업들은 다음 조건을 만족한다.

1. $r_i$ 와 $d_i$ 는 정수이고, $T_i$ 는 정수 시각에 실행된다.
2. $r_i \le r_j$ 인 것과 $d_i \le d_j$ 인 것은 서로 필요충분조건이다.
3. 모든 작업을 각자의 구간 안에서 끝내는 스케줄이 적어도 하나 존재한다.

모든 작업을 스케줄하면서 사용하지 않는 구간의 개수를 최소로 하는 방법을 찾는 프로그램을 작성하시오. 여기서 사용하지 않는 구간이란, 첫 번째 작업이 시작된 시점부터 마지막 작업이 끝나는 시점 사이에서 아무 작업도 실행되지 않는, 서로 이어진 빈 단위 구간들의 한 덩어리를 말한다. 붙어 있는 빈 단위 구간들은 하나로 세며, 사용하지 않는 구간은 첫 번째 작업을 스케줄한 이후부터 센다.

예를 들어 $[r_1, d_1] = [4, 8]$, $[r_2, d_2] = [1, 3]$, $[r_3, d_3] = [8, 10]$, $[r_4, d_4] = [0, 3]$, $[r_5, d_5] = [6, 8]$ 인 작업 다섯 개를 생각하자. 어떤 방식으로 배치하면 사용하지 않는 구간이 3개가 되지만, 더 잘 배치하면 사용하지 않는 구간을 1개까지 줄일 수 있다. 이 경우 최소 개수는 1이다.

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다.

각 테스트 케이스의 첫째 줄에는 작업의 수 $n$ ($1 \le n \le 100000$) 이 주어진다. 이어지는 $n$ 개의 줄에는 각 작업 $T_i$ 의 릴리즈 시간 $r_i$ 와 데드라인 $d_i$ 가 공백으로 구분되어 주어진다. ($0 \le r_i \le d_i \le 1000000$)

각 테스트 케이스마다 사용하지 않는 구간의 최소 개수를 한 줄에 하나씩 출력한다.