Alice merancang sebuah sistem sandi: sistem tersebut menyandikan teks asli (plaintext) sebagai bilangan bulat tak bertanda 64-bit $x$, dan memilih secara acak sebuah bilangan bulat tak bertanda 64-bit $a$ sebagai kunci publik, lalu mengenkripsi teks asli untuk mendapatkan teks sandi (ciphertext) $b = a^x \bmod 2^{64}$. Secara khusus, didefinisikan bahwa $0^0 = 1$.

Sekarang, Bob telah menyadap $n$ pasang informasi terenkripsi $(a_i, b_i)$ ($i = 1, 2, \dots, n$). Untuk mendekripsi semua informasi tersebut, Bob perlu mencari bilangan bulat terkecil $x_i$ ($0 \le x_i < 2^{64}$) untuk setiap pasang informasi terenkripsi sedemikian sehingga $a_i^{x_i} \equiv b_i \pmod{2^{64}}$, atau menentukan bahwa informasi tersebut telah rusak (yaitu tidak ada $x_i$ yang memenuhi syarat). Tuliskan sebuah program untuk membantu Bob menyelesaikan tugas ini.

Masukan

Baris pertama masukan berisi sebuah bilangan bulat $n$ ($1 \le n \le 10^5$), yang menyatakan banyaknya pesan.

Pada $n$ baris berikutnya, baris ke-$i$ berisi dua bilangan bulat $a_i$ dan $b_i$ ($0 \le a_i, b_i < 2^{64}$), yang masing-masing menyatakan kunci publik dan teks sandi dari informasi ke-$i$.

Keluaran

Keluarkan $n$ baris, untuk baris ke-$i$:

• Jika terdapat setidaknya satu $x_i$ yang memenuhi syarat pada soal, keluarkan nilai yang terkecil;
• Jika tidak, keluarkan satu baris broken message.

Contoh

Masukan

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

Keluaran

2
3
994996658310742016
broken message
broken message