Alice suunnitteli salausjärjestelmän: se koodaa selkokielen 64-bittiseksi etumerkittömäksi kokonaisluvuksi $x$, valitsee satunnaisesti 64-bittisen etumerkittömän kokonaisluvun $a$ julkiseksi avaimeksi ja salaa selkokielen salatekstiksi $b = a^x \bmod 2^{64}$. Erityisesti määritellään, että $0^0 = 1$.

Nyt Bob on siepannut $n$ salattua tietoparia $(a_i, b_i)$ ($i = 1, 2, \dots, n$). Purkaakseen kaiken tiedon Bobin täytyy jokaiselle salatulle tietoparille etsiä pienin kokonaisluku $x_i$ ($0 \le x_i < 2^{64}$), jolle $a_i^{x_i} \equiv b_i \pmod{2^{64}}$, tai todeta, että tieto on vioittunut (eli ehtoa toteuttavaa lukua $x_i$ ei ole olemassa). Kirjoita ohjelma, joka auttaa Bobia suorittamaan tämän tehtävän.

Syöte

Syötteen ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 10^5$), joka ilmaisee viestien lukumäärän.

Seuraavista $n$ rivistä $i$:s rivi sisältää kaksi kokonaislukua $a_i$ ja $b_i$ ($0 \le a_i, b_i < 2^{64}$), jotka ilmaisevat $i$:nnen tietoparin julkisen avaimen ja salatekstin.

Tuloste

Tulosta $n$ riviä, $i$:nnelle riville:

• Jos tehtävän ehdot täyttäviä lukuja $x_i$ on olemassa vähintään yksi, tulosta niistä pienin;
• Muussa tapauksessa tulosta rivi broken message.

Esimerkki

Syöte

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

Tuloste

2
3
994996658310742016
broken message
broken message