Alice diseñó un sistema de cifrado: codifica el texto plano como un entero sin signo de 64 bits $x$, selecciona aleatoriamente un entero sin signo de 64 bits $a$ como clave pública y cifra el texto plano para obtener el texto cifrado $b = a^x \bmod 2^{64}$. En particular, se define que $0^0 = 1$.

Ahora, Bob ha interceptado $n$ conjuntos de información cifrada $(a_i, b_i)$ ($i = 1, 2, \dots, n$). Para descifrar toda la información, Bob necesita encontrar, para cada conjunto de información cifrada, el menor entero $x_i$ ($0 \le x_i < 2^{64}$) tal que $a_i^{x_i} \equiv b_i \pmod{2^{64}}$, o determinar que la información se ha corrompido (es decir, que no existe ningún $x_i$ que cumpla la condición). Por favor, escribe un programa para ayudar a Bob a realizar esta tarea.

Entrada

La primera línea de la entrada contiene un entero $n$ ($1 \le n \le 10^5$), que representa el número de mensajes.

En las siguientes $n$ líneas, la $i$-ésima línea contiene dos enteros $a_i$ y $b_i$ ($0 \le a_i, b_i < 2^{64}$), que representan respectivamente la clave pública y el texto cifrado del $i$-ésimo conjunto de información.

Salida

Imprime $n$ líneas; para la $i$-ésima línea:

• Si existe al menos un $x_i$ que satisfaga las condiciones indicadas en el problema, imprime el menor de ellos;
• En caso contrario, imprime una línea con broken message.

Ejemplo

Entrada

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

Salida

2
3
994996658310742016
broken message
broken message