Alice hat ein Verschlüsselungssystem entworfen: Es kodiert den Klartext als vorzeichenlose 64-Bit-Ganzzahl $x$, wählt zufällig eine vorzeichenlose 64-Bit-Ganzzahl $a$ als öffentlichen Schlüssel aus und verschlüsselt den Klartext zum Geheimtext $b = a^x \bmod 2^{64}$. Insbesondere ist $0^0 = 1$ definiert.

Nun hat Bob $n$ Sätze verschlüsselter Informationen $(a_i, b_i)$ ($i = 1, 2, \dots, n$) abgefangen. Um alle Informationen zu entschlüsseln, muss Bob für jeden Satz verschlüsselter Informationen die kleinste Ganzzahl $x_i$ ($0 \le x_i < 2^{64}$) finden, sodass $a_i^{x_i} \equiv b_i \pmod{2^{64}}$ gilt, oder feststellen, dass die Information beschädigt wurde (d. h., es gibt kein $x_i$, das die Bedingung erfüllt). Bitte schreibe ein Programm, um Bob bei dieser Aufgabe zu helfen.

Eingabe

Die erste Zeile der Eingabe enthält eine Ganzzahl $n$ ($1 \le n \le 10^5$), die die Anzahl der Nachrichten darstellt.

In den nächsten $n$ Zeilen enthält die $i$-te Zeile zwei Ganzzahlen $a_i$ und $b_i$ ($0 \le a_i, b_i < 2^{64}$), die den öffentlichen Schlüssel bzw. den Geheimtext des $i$-ten Informationssatzes darstellen.

Ausgabe

Gib $n$ Zeilen aus, für die $i$-te Zeile:

• Falls mindestens ein $x_i$ existiert, das die in der Aufgabe genannten Bedingungen erfüllt, gib das kleinste davon aus;
• Andernfalls gib eine Zeile mit broken message aus.

Beispiel

Eingabe

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

Ausgabe

2
3
994996658310742016
broken message
broken message