Аліса розробила криптосистему: вона кодує відкритий текст у вигляді 64-бітного беззнакового цілого числа $x$, випадковим чином вибирає 64-бітне беззнакове ціле число $a$ як відкритий ключ і шифрує відкритий текст, отримуючи шифротекст $b = a^x \bmod 2^{64}$. Зокрема, вважається, що $0^0 = 1$.

Тепер Боб перехопив $n$ наборів зашифрованої інформації $(a_i, b_i)$ ($i = 1, 2, \dots, n$). Щоб розшифрувати всю інформацію, Бобу потрібно для кожного набору зашифрованої інформації знайти найменше ціле число $x_i$ ($0 \le x_i < 2^{64}$), таке що $a_i^{x_i} \equiv b_i \pmod{2^{64}}$, або визначити, що інформацію було пошкоджено (тобто не існує $x_i$, яке задовольняє умову). Будь ласка, напишіть програму, яка допоможе Бобу виконати це завдання.

Вхідні дані

Перший рядок вхідних даних містить ціле число $n$ ($1 \le n \le 10^5$) — кількість повідомлень.

У наступних $n$ рядках $i$-й рядок містить два цілі числа $a_i$ та $b_i$ ($0 \le a_i, b_i < 2^{64}$), що позначають відкритий ключ і шифротекст $i$-го набору інформації відповідно.

Вихідні дані

Виведіть $n$ рядків, для $i$-го рядка:

• Якщо існує принаймні одне $x_i$, що задовольняє умови задачі, виведіть найменше з них;
• Інакше виведіть рядок broken message.

Приклад

Вхідні дані

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

Вихідні дані

2
3
994996658310742016
broken message
broken message