Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0217 - MOST

   Several years ago, the African tribe of Hooligans dug up a hatchet. The tribe’s military uses advanced technology including machine guns and tanks. Such an equipment gives a huge advan- tage against the enemy, but it also brings complications during transport. The biggest problem are the numerous rivers and lakes present in the area.

   Hooligan cartographers invented a precise transformation that maps the landscape in such a way that all boundaries between land and water are either vertical or horizontal and follow precisely the boundaries of unit squares in a square grid. Moreover, the special transformation algorithm causes all rivers to appear to flow vertically (from top to bottom) and all coordinates of the left river boundary are strictly smaller than any coordinate of the right boundary.

   Luckily for the ambitious Hooligans, a great inventor named Postolomlatos invented mobile bridges made of easily transportable pieces, called pontoons, precisely of the size of the unit squares of the map. The pontoons can be connected to each other and to the river boundaries only by their whole sides. Due to the economical crisis, the chief Mlask the Great ordered that every river must be crossed by using the minimal number of pontoons needed to build a connected bridge from one side of the river to the other.

   See the image with an example of a river with one possible correct solution using three pontoons.

 

Input

   The first line of the input contains the number of test cases N . The first line of each test case contains a positive integer K 10 000 000, which stands for the height of the map. Each of the following K lines describes one horizontal unit strip of the map. Each of these lines contains two space-separated non-negative integers A and B specifying the left and the right coordinates of the river boundary in that strip. It will always hold that A < B 1 000 000.

Output

   For each test case, print exactly one line containing the text K prechodu reky je treba X pontonu.”, where X is the smallest number of pontoons needed to build a bridge from one side of the river to the other.

Examples

stdin

stdout

1

2
8
2 8
3 9
4 9
4 8
2 7
1 5
1 6
0 5
5
1 7
2 7
4 8
5 6
0 6

K prechodu reky je treba 3 pontonu.
K prechodu reky je treba 1 pontonu.

Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2014-10-08
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.CTU Open 2014.B

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.