Alice zaprojektowała system szyfrowania: koduje on tekst jawny jako 64-bitową liczbę całkowitą bez znaku $x$, losowo wybiera 64-bitową liczbę całkowitą bez znaku $a$ jako klucz publiczny i szyfruje tekst jawny, otrzymując szyfrogram $b = a^x \bmod 2^{64}$. W szczególności przyjmujemy, że $0^0 = 1$.

Teraz Bob przechwycił $n$ zestawów zaszyfrowanych informacji $(a_i, b_i)$ ($i = 1, 2, \dots, n$). Aby odszyfrować wszystkie informacje, Bob musi dla każdego zestawu zaszyfrowanych informacji znaleźć najmniejszą liczbę całkowitą $x_i$ ($0 \le x_i < 2^{64}$) taką, że $a_i^{x_i} \equiv b_i \pmod{2^{64}}$, lub stwierdzić, że informacja została uszkodzona (tzn. nie istnieje $x_i$ spełniające warunek). Napisz program, który pomoże Bobowi wykonać to zadanie.

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą $n$ ($1 \le n \le 10^5$), oznaczającą liczbę wiadomości.

W kolejnych $n$ wierszach $i$-ty wiersz zawiera dwie liczby całkowite $a_i$ oraz $b_i$ ($0 \le a_i, b_i < 2^{64}$), oznaczające odpowiednio klucz publiczny i szyfrogram $i$-tego zestawu informacji.

Wyjście

Wypisz $n$ wierszy; w $i$-tym wierszu:

• Jeśli istnieje co najmniej jedno $x_i$ spełniające warunki zadania, wypisz najmniejsze z nich;
• W przeciwnym razie wypisz wiersz broken message.

Przykład

Wejście

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

Wyjście

2
3
994996658310742016
broken message
broken message