1. Trefa do čierneho

Rozpálené slnko už pár dní pieklo, a tak sa Emo so Samom rozhodli, že sa uchýlia do klimatizovanej haly a zahrajú si partičku squashu. Emo využíval všetky svoje tenisové schopnosti. Keď raz napriahol ruku a švihol raketou v snahe odbiť loptičku, trafil miesto nej Samovu nohu. Tak bol ich zápas predčasne ukončený a každý išiel späť svojou cestou.

Samo sa teraz potrebuje vrátiť na internát, ktorý sa nachádza od haly smerom presne na severovýchod. Najradšej by išiel najkratšou trasou – priamo na severovýchod. Keďže po zničujúcom údere jeho noha nie je úplne v poriadku, nie celkom sa mu to darí. Chvíľu poskakuje na svojej zdravej ľavej nohe, no vtedy namiesto toho, aby išiel na severovýchod, ide smerom na východ. Chvíľu potom kráča po oboch a vtedy sa mu darí kráčať na sever. Potom ho noha ale zase začne bolieť a musí poskakovať, a teda ísť na východ. Toto sa dookola opakuje a Samo teda miesto priamo na severovýchod ide cik-cak, raz na východ, raz na sever.

Keďže si Samo nie je istý, či sa takto vôbec dostane na internát, zaujímalo by ho, koľkokrát by pretol svoju ideálnu trasu (polpriamku idúcu od haly na severovýchod), ak by takýmto spôsobom pokračoval donekonečna.

Úloha

Samo sa na začiatku nachádza v bode \((0,0)\) súradnicovej sústavy. Jeho pohyb sa dá popísať pomocou dvoch čísel \(d_x\) a \(d_y\). Samo postupne donekonečna opakuje dva posuny:

• Posun o \(d_x\) metrov smerom na východ (v smere rastúcej \(x\)-ovej súradnice)
• Posun o \(d_y\) metrov smerom na sever (v smere rastúcej \(y\)-ovej súradnice)

Vašou úlohou je zistiť, koľkokrát takto pretne priamku \(x=y\), pričom za pretnutie rátame aj dotyk s priamkou.

Formát vstupu

Aby sme mohli presnejšie testovať rýchlosť vašich riešení, v každom testovacom vstupe bude potrebné vyriešiť úlohu pre viacero dvojíc \(d_x, d_y\).

Na prvom riadku vstupu bude číslo \(t ~ (1 \leq t \leq 1000)\), určujúce počet zadaní úlohy, ktoré treba vyriešiť. Nasleduje \(t\) riadkov, každý z nich obsahuje dve celé čísla \(d_x, d_y ~ (1 \leq d_x, d_y \leq 10^{15})\) oddelené medzerou: číslo \(d_x\) predstavujúce dĺžku posunu smerom na východ a číslo \(d_y\) predstavujúce dĺžku posunu smerom na sever.

Formát výstupu

Pre každú zadanú dvojicu \(d_x, d_y\) vypíšte do samostatného riadku počet pretnutí Samovej cesty s priamkou \(x=y\). V prípade, že priamku cesta pretne nekonečne veľa ráz, vypíšte \(-1\). Nezabudnite vypísať znak konca riadku aj za posledným riadkom výstupu.

Hodnotenie

Vaše riešenia budú testované na štyroch sadách testovacích vstupov, pre ktoré platí:

Všimnite si, že čísla \(d_x\) a \(d_y\) presiahnu \(2^{31} - 1\) (zhruba \(2\cdot 10^9\)), čo je najväčšie číslo, ktoré sa dá uložiť v \(32\)-bitovej premennej so znamienkom. Použite preto \(64\)-bitové premenné typu long long v C++ a Int64 v Pascale.

Príklad

Input:

2
1 1
3 2

Output:

-1
1

Pri prvej ceste sa Samo priamky dotkne nekonečne veľa ráz. Pri druhej ceste sa priamky dotkne iba v bode \((0, 0)\).