Alice a conçu un système de chiffrement : il encode le texte en clair sous la forme d'un entier non signé sur 64 bits $x$, choisit aléatoirement un entier non signé sur 64 bits $a$ comme clé publique, et chiffre le texte en clair pour obtenir le texte chiffré $b = a^x \bmod 2^{64}$. En particulier, on définit $0^0 = 1$.

Maintenant, Bob a intercepté $n$ paires d'informations chiffrées $(a_i, b_i)$ ($i = 1, 2, \dots, n$). Pour déchiffrer toutes les informations, Bob doit trouver, pour chaque paire d'informations chiffrées, le plus petit entier $x_i$ ($0 \le x_i < 2^{64}$) tel que $a_i^{x_i} \equiv b_i \pmod{2^{64}}$, ou déterminer que l'information a été corrompue (c'est-à-dire qu'il n'existe aucun $x_i$ satisfaisant la condition). Veuillez écrire un programme pour aider Bob à accomplir cette tâche.

Entrée

La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 10^5$), représentant le nombre de messages.

Parmi les $n$ lignes suivantes, la $i$-ème ligne contient deux entiers $a_i$ et $b_i$ ($0 \le a_i, b_i < 2^{64}$), représentant respectivement la clé publique et le texte chiffré du $i$-ème message.

Sortie

Affichez $n$ lignes ; pour la $i$-ème ligne :

• S'il existe au moins un $x_i$ qui satisfait les conditions de l'énoncé, affichez le plus petit d'entre eux ;
• Sinon, affichez une ligne contenant broken message.

Exemple

Entrée

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

Sortie

2
3
994996658310742016
broken message
broken message