역사 시간

현수는 서강대학교에서 한국사를 강의하는 교수이다. 강의할 역사적 사건은 $n$개이고, 한 수업 시간에 사건을 하나씩 다룬다. 이제 수업마다 어떤 사건을 강의할지 순서를 정해야 한다.

$i$번째 사건은 구간 $[a_i, b_i]$ 동안 일어났다. 두 사건의 구간이 한 점이라도 공유하면 두 사건은 서로 연관되었다고 한다. 연관된 사건을 가까운 수업에서 강의하면 학생들의 이해도가 높아진다. 연관되지 않은 두 사건은 일어난 순서를 지켜 강의해야 한다. 즉 A와 B가 연관되지 않았고 A가 B보다 먼저 일어났다면, A를 B보다 먼저 강의해야 한다.

$i$번째 수업과 $j$번째 수업 사이의 거리는 $|i - j|$이다. 강의 순서를 하나 정했을 때, 연관된 두 사건이 떨어진 거리의 최댓값을 $k$라고 하자. 위 규칙을 지키는 강의 순서 중에서 $k$의 최솟값을 구하는 프로그램을 작성하시오. 연관된 사건 쌍이 하나도 없으면 $k$는 $0$이다.

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

각 테스트 케이스의 첫째 줄에 사건의 개수 $n$ ($1 \le n \le 50000$)이 주어진다. 이어지는 $n$개 줄에 사건이 일어난 구간의 양 끝 $a_i$와 $b_i$가 주어진다 ($-10^9 \le a_i \le b_i \le 10^9$). 구간이 서로 같은 두 사건은 없다.

각 테스트 케이스마다 $k$의 최솟값을 한 줄에 출력한다.