Zadanie

Francúzske okno

Počet bodov: 45

Leto k nám letí nesmiernou rýchlosťou a s ním k nám nielen obrovskou rýchlosťou, ale aj počtom priletia húfy a hejná komárov. Asi by bolo fajn nainštalovať si na okno v izbe tú sieťku ktorú ste si chceli definitívne namontovať už minulý rok, keďže rok pred tým to už bolo piate výročie od kedy ste sa rozhodli, že to v ten rok určite spravíte. Ako ten čas letí…

Úloha

Kvôli lockdownu nemôžete ísť do obchodu a tak si sieťku musíte zostrojiť sami. Okno na ktoré chcete sieťku umiestniť má tvar obdĺžnika (s celočíselnými rozmermi) a po svojom obvode má v pravidelných 1mm rozostupoch rozmiestnené háčiky cez ktoré môžete viesť nylonovú šnúru. Háčiky sú v každom zo štyroch rohov okna. Cieľom je medzi háčikmi upevniť šnúry tak aby vo vzniknutej sieti neexistovala diera väčšia ako komár - to docielime tak, že každým bodom okna (vnútorným aj obvodovým) s celočíselnými súradnicami prechádza aspoň jedna šnúra. Šnúry budete viesť vždy diagonálne (inak by sieťka vyzerala otrasne), pričom rámu okna sa môže dotýkať iba v mieste kde je umiestnený háčik.

Postup naťahovania jednej šnúry je nasledovný. Odstrihnete si dlhočízny kusisko šnúry a upevníte ho na ľubovolnom háčiku. Potom ju začnete ťahať v diagonálnom smere (teda voči rámu okna budete zvierať 45° uhol). Ak narazíte na iný háčik, môžete spraviť jednu z troch možností

1. môžete tu šnúru upevniť a proces naťahovania tak ukončiť
2. môžete šnúru naťahovať smerom akým ste prišli
3. môžete šnúru naťahovať smerom kolmým na smer akým ste prišli (ale iba tak aby ste so šnúrou nevyšli mimo okna, teda napríklad v rohoch túto možnosť nemôžete využiť)

Nylónovej šnúry máte v klbku v pivnici rádovo niekoľko kilometrov, takže sa ňou nemusíte báť plytvať. Nožnice máte však iba jedny a už vieme, že keď o ne prídete tak si nemáte ako kúpiť ďalšie. Teda s dlhou životnosťou v mysli chcete odstrihnúť čo najmenej kusísk. Koľko ich bude?

Formát vstupu

Na prvom riadku vstupu máte jedno celé číslo \(0 \le O \le 10^4\), počet okien pre ktoré budete vyrábať sieťky.

Nasleduje \(O\) riadkov, na každom z nich dve celé čísla \(2 \le N, M \le 7^{10}+9\) udávajúce počet háčikov na horizontálnej a vertikálnej strane okna (teda okno má rozmery \((N-1) \times (M-1)\)mm).

Formát výstupu

Na výstup vypíšte \(O\) riadkov. Na \(i\)-tom z nich odpoveď na otázku “Koľko najmenej šnúr potrebujeme na vytvorenie dobrej sieťky na \(i\)-tom okne”.

Príklad

Input:

7
2 2
3 3
3 4
3 5
4 5
7 9
4 7

Output:

2
3
2
3
2
3
4

Na obrázku vidíme jedno z optimálnych poťahaní šnúr. Všimnime si, že štvorcom označeným ružovým kruhom neprechádza žiadna šnúra, ale cez všetky jeho rohy áno, čo je postačujúce