경합

영화관 앞줄 좌석을 판매하고 있습니다. 앞줄에는 N개의 좌석이 있으며, 왼쪽에서 오른쪽으로 1번부터 N번까지 번호가 붙어 있습니다. 지난 일주일 동안 사무실을 비웠는데, 돌아와 보니 좌석 예약 Q건이 쌓여 있습니다. i번째 예약은 $L_i$번부터 $R_i$번까지의 모든 좌석을 요청합니다. 이제 예약을 하나씩 시스템에 입력하는 일을 해야 합니다.

예약끼리 겹칠 수 있어서 시스템이 모든 예약을 빠짐없이 처리하지 못할 수도 있습니다. 예약을 입력하면 시스템은 그 예약이 요청한 좌석 중, 앞에서 입력된 예약에 아직 배정되지 않은 좌석을 모두 배정합니다.

각 예약에 최소 $k$석 이상이 배정되도록 예약을 입력할 수 있는 순서가 존재하는 정수 $k$의 최댓값을 구하십시오.

입력의 첫 줄에 테스트 케이스의 수 $T$가 주어집니다. 이어서 $T$개의 테스트 케이스가 나옵니다. 각 테스트 케이스의 첫 줄에는 좌석 수 $N$과 예약 수 $Q$가 두 정수로 주어집니다. 그 다음 $Q$개의 줄에서 i번째 줄에는 두 정수 $L_i$, $R_i$가 주어지며, 이는 i번째 예약이 $L_i$번부터 $R_i$번까지의 모든 좌석을 요청함을 뜻합니다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력합니다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 위에서 설명한 최댓값 $k$입니다.

$T = 100$.

$1 \le N \le 10^6$.

$1 \le L_i \le R_i \le N$.

어떤 예약에도 포함되지 않는 좌석이 있을 수 있습니다. 이런 좌석은 예약 배정에 영향을 주지 않습니다. 예약 중 하나라도 좌석을 한 석도 배정받지 못하는 경우, 답은 0입니다.