Alice ha progettato un sistema crittografico: codifica il testo in chiaro come un intero senza segno a 64 bit $x$, seleziona casualmente un intero senza segno a 64 bit $a$ come chiave pubblica e cifra il testo in chiaro ottenendo il testo cifrato $b = a^x \bmod 2^{64}$. In particolare, si definisce $0^0 = 1$.

Ora, Bob ha intercettato $n$ coppie di informazioni cifrate $(a_i, b_i)$ ($i = 1, 2, \dots, n$). Per decifrare tutte le informazioni, per ciascuna coppia di informazioni cifrate Bob deve trovare il più piccolo intero $x_i$ ($0 \le x_i < 2^{64}$) tale che $a_i^{x_i} \equiv b_i \pmod{2^{64}}$, oppure stabilire che l'informazione è stata corrotta (ossia non esiste alcun $x_i$ che soddisfi la condizione). Scrivi un programma per aiutare Bob a portare a termine questo compito.

Input

La prima riga dell'input contiene un intero $n$ ($1 \le n \le 10^5$), che rappresenta il numero di messaggi.

Nelle successive $n$ righe, la $i$-esima riga contiene due interi $a_i$ e $b_i$ ($0 \le a_i, b_i < 2^{64}$), che rappresentano rispettivamente la chiave pubblica e il testo cifrato dell'$i$-esimo insieme di informazioni.

Output

Stampa $n$ righe; per la $i$-esima riga:

• Se esiste almeno un $x_i$ che soddisfa le condizioni indicate nel problema, stampa il più piccolo;
• Altrimenti, stampa una riga contenente broken message.

Esempio

Input

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

Output

2
3
994996658310742016
broken message
broken message