Alice har designet et chiffersystem: det koder klarteksten som et 64-biters fortegnsløst heltall $x$, velger tilfeldig et 64-biters fortegnsløst heltall $a$ som offentlig nøkkel, og krypterer klarteksten for å få chifferteksten $b = a^x \bmod 2^{64}$. Spesielt defineres $0^0 = 1$.

Nå har Bob fanget opp $n$ sett med kryptert informasjon $(a_i, b_i)$ ($i = 1, 2, \dots, n$). For å dekryptere all informasjonen må Bob for hvert sett med kryptert informasjon finne det minste heltallet $x_i$ ($0 \le x_i < 2^{64}$) slik at $a_i^{x_i} \equiv b_i \pmod{2^{64}}$, eller fastslå at informasjonen er blitt ødelagt (dvs. at det ikke finnes noen $x_i$ som oppfyller betingelsen). Skriv et program for å hjelpe Bob med å løse denne oppgaven.

Inndata

Den første linjen i inndataene inneholder et heltall $n$ ($1 \le n \le 10^5$), som representerer antallet meldinger.

I de neste $n$ linjene inneholder den $i$-te linjen to heltall $a_i$ og $b_i$ ($0 \le a_i, b_i < 2^{64}$), som representerer henholdsvis den offentlige nøkkelen og chifferteksten for det $i$-te informasjonssettet.

Utdata

Skriv ut $n$ linjer, for den $i$-te linjen:

• Hvis det finnes minst én $x_i$ som oppfyller betingelsene i oppgaven, skriv ut den minste av dem;
• Ellers, skriv ut en linje med broken message.

Eksempel

Inndata

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

Utdata

2
3
994996658310742016
broken message
broken message