Nessie nyomában

A Loch Ness-i szörny egy rejtélyes és ismeretlen állat. Azt mondják róla, hogy a Loch Ness-i tóban él, amely egy nagyon mély, édesvízű tó Inverness városa mellett, Észak-Skóciában. Nessie-t rendszerint a tavi szörnyek közé szokták besorolni.

(http://en.wikipedia.org/wiki/Loch_Ness_Monster)

2003 júliusában a BBC a Loch Ness-i tó minden részére kiterjedő vizsgálatot végzett. A vizsgálathoz 600 radarsugarat használtak, de semmi nyomát nem találták „tengeri szörnynek” (pontosabban semmilyen nagy, ismert vagy ismeretlen állatnak) a tóban. A BBC csapata megállapította, hogy Nessie nem létezik. Most szeretnénk megismételni a kísérletet.

Adott egy n soros és m oszlopos rács, amely a tavat reprezentálja (6 ≤ n, m ≤ 10000). Határozd meg a legkisebb olyan s számot, amely megmondja, hogy hány radart kell a négyzetrácsra helyeznünk ahhoz, hogy ellenőrizhessük a rács minden celláját, a következő feltételekkel:

1. Minden radar egy cellát foglal el a rácson, miközben a saját celláját, illetve a vele szomszédos cellákat ellenőrzi.
2. A rács szélén lévő cellákat nem kell lefedni, mivel Nessie úgysem tudna oda elbújni (ahhoz ugyanis túl nagy).

Például az ábrákon az X egy radart reprezentál, míg az árnyékolt cellák a radarok által lefedett cellákat mutatják. Az utolsó ábra egy lehetséges megoldást ábrázol.

A bemenet specifikációja

A bemenet első sora egy t egész számot tartalmaz, amely a tesztesetek számát jelzi. Minden tesztesethez tartozik egy sor, amelyben két, egymástól szóközökkel elválasztott szám található (6 ≤ n, m ≤ 10000), melyek a rács méretét adják meg (n sor és m oszlop).

A kimenet specifikációja

A kimenetnek minden tesztesetre egy sort kell tartalmaznia, amelyben a legkisebb olyan radarszám áll, amely teljesíti a fenti feltételeket.

Példa bemenet

1. 3
2. 6 6
3. 7 7
4. 9 13

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

A példa bemenethez tartozó kimenet

1. 4
2. 4
3. 12

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