부교 놓기

몇 해 전 훌리건 부족이 전쟁을 일으켰다. 훌리건 군대는 기관총과 전차를 옮기기 때문에 이 지역에 많은 강을 건너는 일이 행군에서 가장 어렵다. 훌리건 지도 제작자는 땅과 물의 경계가 모두 정사각형 격자의 단위 정사각형 변을 따라가도록 지형을 다시 그린다. 이렇게 그린 지도에서 강은 위에서 아래로 곧게 흐르고, 왼쪽 기슭의 좌표는 모두 오른쪽 기슭의 좌표보다 작다.

발명가 포스톨로믈라토스는 폰툰으로 이동식 다리를 만든다. 폰툰 하나는 물인 단위 정사각형 하나를 정확히 덮는다. 두 폰툰은 한 변을 온전히 맞댈 때만 서로 붙고, 폰툰은 땅인 정사각형과 한 변을 온전히 맞댈 때만 기슭에 닿는다. 족장 믈라스크 대왕은 강마다 폰툰을 가장 적게 써서 건너라고 명령했다.

강 하나의 지도는 높이가 단위 띠 $K$개다. 띠는 위에서 아래로 $1$번부터 $K$번까지 번호를 붙인다. $i$번 띠에서 물은 가로 좌표 $A_i$부터 $B_i$까지를 덮으므로, 그 띠에서 물인 정사각형은 $(i, A_i), (i, A_i + 1), \dots, (i, B_i - 1)$이다. 여기서 $(i, x)$는 $i$번 띠에서 세로선 $x$와 $x + 1$ 사이에 놓인 정사각형이다. $i$번 띠에서 좌표가 $A_i$보다 작은 정사각형은 왼쪽 기슭이고, 좌표가 $B_i$ 이상인 정사각형은 오른쪽 기슭이다. $1$번 띠 위와 $K$번 띠 아래에는 아무것도 없다.

물인 정사각형의 집합 $S$는 다음 세 조건을 모두 만족할 때 다리다.

• $S$의 임의의 두 정사각형은 $S$의 정사각형을 이어 만든 사슬로 연결되고, 사슬에서 이웃한 두 정사각형은 한 변을 온전히 맞댄다.
• $S$의 어떤 정사각형이 왼쪽 기슭의 정사각형과 한 변을 온전히 맞댄다.
• $S$의 어떤 정사각형이 오른쪽 기슭의 정사각형과 한 변을 온전히 맞댄다.

왼쪽 기슭에 닿는 정사각형과 오른쪽 기슭에 닿는 정사각형이 같은 띠에 있어도 되고 다른 띠에 있어도 된다. 다리가 가질 수 있는 정사각형 개수의 최솟값을 구하라.

첫 줄에 테스트 케이스의 수 $N$이 주어진다. 각 테스트 케이스의 첫 줄에는 지도의 높이인 양의 정수 $K \le 10\,000\,000$이 주어진다. 이어지는 $K$개의 줄은 위에서 아래로 단위 띠를 하나씩 설명하며, 각 줄에는 그 띠에서 기슭의 왼쪽 좌표와 오른쪽 좌표인 두 정수 $A_i$와 $B_i$가 공백으로 구분되어 주어진다. 항상 $0 \le A_i < B_i \le 1\,000\,000$이고, 모든 $A_i$는 모든 $B_j$보다 작다.

각 테스트 케이스마다 다음 한 줄을 출력한다.

K prechodu reky je treba X pontonu.

$X$ 자리에는 강의 한쪽 기슭에서 다른 쪽 기슭까지 다리를 놓는 데 필요한 폰툰의 최소 개수를 넣는다. 문장은 발음 구별 기호가 없는 체코어 그대로, 보기와 똑같이 출력한다. 줄 맨 앞의 K는 체코어 전치사이고 지도의 높이가 아니다.