Pontoon Bridge

Some years ago the Hooligan tribe went to war. Their army moves machine guns and tanks, so crossing the many rivers of the region is the hardest part of every march. Hooligan cartographers redraw the land so that every boundary between land and water runs along the sides of the unit squares of a square grid. On such a map every river flows straight down, and every coordinate of the left bank is smaller than every coordinate of the right bank.

The inventor Postolomlatos builds mobile bridges out of pontoons. One pontoon covers exactly one unit square of water. Two pontoons hold together only when they share a whole side, and a pontoon reaches a bank only when it shares a whole side with a square of land. Chief Mlask the Great wants every river crossed with as few pontoons as possible.

The map of one river is $K$ unit strips high. The strips are numbered $1$ to $K$ from top to bottom. In strip $i$ the water covers the horizontal coordinates from $A_i$ to $B_i$, so the water squares of that strip are $(i, A_i), (i, A_i + 1), \dots, (i, B_i - 1)$, where $(i, x)$ is the square of strip $i$ between the vertical lines $x$ and $x + 1$. In strip $i$ every square with coordinate smaller than $A_i$ belongs to the left bank, and every square with coordinate at least $B_i$ belongs to the right bank. Nothing exists above strip $1$ or below strip $K$.

A set $S$ of water squares is a bridge when all three conditions hold.

• Any two squares of $S$ are joined by a chain of squares of $S$ in which consecutive squares share a whole side.
• Some square of $S$ shares a whole side with a square of the left bank.
• Some square of $S$ shares a whole side with a square of the right bank.

The square that touches the left bank and the square that touches the right bank may lie in different strips. Compute the smallest number of squares a bridge can have.

The first line contains the number of test cases $N$. The first line of each test case contains one positive integer $K \le 10\,000\,000$, the height of the map. Each of the next $K$ lines describes one horizontal unit strip, from top to bottom, and contains two space separated integers $A_i$ and $B_i$: the left and the right coordinate of the river bank in that strip. Always $0 \le A_i < B_i \le 1\,000\,000$, and every $A_i$ is smaller than every $B_j$.

For each test case print exactly one line:

K prechodu reky je treba X pontonu.

Replace $X$ with the smallest number of pontoons that build a bridge from one bank of the river to the other. Print the sentence exactly as shown, in Czech and without diacritics. The K at the start of the line is the Czech preposition, not the height of the map.