Alice hannaði dulmálskerfi: það kóðar lesmálið sem 64-bita formerkjalausa heiltölu $x$, velur af handahófi 64-bita formerkjalausa heiltölu $a$ sem dreifilykil og dulkóðar lesmálið til að fá dulmálið $b = a^x \bmod 2^{64}$. Sérstaklega er skilgreint að $0^0 = 1$.

Nú hefur Bob hlerað $n$ sett af dulkóðuðum upplýsingum $(a_i, b_i)$ ($i = 1, 2, \dots, n$). Til að afkóða allar upplýsingarnar þarf Bob, fyrir hvert sett af dulkóðuðum upplýsingum, að finna minnstu heiltöluna $x_i$ ($0 \le x_i < 2^{64}$) þannig að $a_i^{x_i} \equiv b_i \pmod{2^{64}}$, eða komast að því að upplýsingarnar hafi skemmst (þ.e. engin slík tala $x_i$ uppfyllir skilyrðið). Vinsamlegast skrifið forrit til að hjálpa Bob að leysa þetta verkefni.

Inntak

Fyrsta lína inntaksins inniheldur heiltölu $n$ ($1 \le n \le 10^5$), sem táknar fjölda skilaboða.

Í næstu $n$ línum inniheldur $i$-ta línan tvær heiltölur $a_i$ og $b_i$ ($0 \le a_i, b_i < 2^{64}$), sem tákna dreifilykil og dulmál $i$-ta upplýsingasettsins.

Úttak

Prentið $n$ línur, og í $i$-tu línu:

• Ef til er að minnsta kosti eitt $x_i$ sem uppfyllir skilyrði dæmisins skal prenta það minnsta;
• Annars skal prenta línuna broken message.

Dæmi

Inntak

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

Úttak

2
3
994996658310742016
broken message
broken message