Alice har konstruerat ett chiffersystem: det kodar klartexten som ett 64-bitars teckenlöst heltal $x$, väljer slumpmässigt ett 64-bitars teckenlöst heltal $a$ som publik nyckel och krypterar klartexten för att få chiffertexten $b = a^x \bmod 2^{64}$. Speciellt definieras $0^0 = 1$.

Nu har Bob snappat upp $n$ uppsättningar krypterad information $(a_i, b_i)$ ($i = 1, 2, \dots, n$). För att dekryptera all information behöver Bob för varje uppsättning krypterad information hitta det minsta heltalet $x_i$ ($0 \le x_i < 2^{64}$) sådant att $a_i^{x_i} \equiv b_i \pmod{2^{64}}$, eller avgöra att informationen har skadats (d.v.s. att det inte finns något $x_i$ som uppfyller villkoret). Skriv ett program som hjälper Bob att utföra denna uppgift.

Indata

Den första raden i indatan innehåller ett heltal $n$ ($1 \le n \le 10^5$), som representerar antalet meddelanden.

På de följande $n$ raderna innehåller den $i$:te raden två heltal $a_i$ och $b_i$ ($0 \le a_i, b_i < 2^{64}$), som representerar den publika nyckeln respektive chiffertexten för den $i$:te informationsuppsättningen.

Utdata

Skriv ut $n$ rader, där den $i$:te raden ska innehålla:

• Om det finns minst ett $x_i$ som uppfyller villkoren i problemet, skriv ut det minsta av dem;
• Annars, skriv ut en rad med broken message.

Exempel

Indata

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

Utdata

2
3
994996658310742016
broken message
broken message