C — A fűnyíró

Mirko szeretne vásárolni egy telket, amelyen házat fog építeni a családjának. Eddig K telket nézett meg. Ezek mindegyike téglalap alakú, azaz egy N sorból és M oszlopból álló mátrixnak tekinthető, N × M mezővel.

Mirko tudja, hogy mielőtt elkezdődik az építkezés, a területet rendszeresen karban kell tartani, le kell nyírni a füvet. Vásárolt tehát egy fűnyírót. Ahhoz, hogy lenyírja az N soros és M oszlopos gyepet, minden mezőt érintenie kell legalább egyszer. Bármelyik mezőről indulhat, a négy fő irány egyike felé (felfelé, lefelé, balra vagy jobbra) nézve. A fűnyírója csak előrefelé tud haladni (az aktuális irányban a szomszédos mezőre) vagy el tud fordulni 90 fokkal. A saját biztonsága érdekében továbbá Mirko csak a saját földjén használhatja a fűnyírót, azaz nem hagyhatja el a mátrixot.

Mivel nem könnyű a fűnyírót elfordítani, Mirko a lehető legkevesebb fordulóval szeretné lenyírni a füvet. Mirko minden eddig megtekintett telek esetében tudni szeretné, hogy minimálisan hány fordulóval lehet lenyírni az adott telken a teljes gyepet. Segíts Mirkónak a feladat megoldásában!

A bemenet specifikációja

A bemenet első sora egy K egész számot tartalmaz (1 ≤ K ≤ 50 000), amely a Mirko által eddig megtekintett telkek számát adja meg.

A következő K sor mindegyikében két pozitív egész szám, N és M, a telek sorainak és oszlopainak a száma szerepel (1 ≤ N, M ≤ 1 000 000).

A kimenet specifikációja

A Mirko által eddig megtekintett minden egyes telekre egyetlen sort kell a kimenetre írni, amely a telken lévő teljes gyep lenyírásához szükséges fordulók minimális számát adja meg.

1. példa bemenet

1. 2
2. 1 10
3. 10 1

letöltés szöveges állományként

Az 1. példa bemenethez tartozó kimenet

1. 0
2. 0

letöltés szöveges állományként

2. példa bemenet

1. 3
2. 1 1
3. 3 3
4. 3 4

letöltés szöveges állományként

A 2. példa bemenethez tartozó kimenet

1. 0
2. 4
3. 4

letöltés szöveges állományként

3. példa bemenet

1. 2
2. 5 8
3. 6 4

letöltés szöveges állományként

A 3. példa bemenethez tartozó kimenet

1. 8
2. 6

letöltés szöveges állományként

Az 1. példa magyarázata

Az első telek forduló nélkül is lenyírható, ha Mirko a telek első oszlopából indul, jobbra néz, és végig előrefelé halad. Hasonló ötlet alkalmazható a második telekre is.

Eredeti feladat

Croatian Open Competition in Informatics 2017/2018, Contest #2, Kosnja