Алиса разработала криптосистему: она кодирует открытый текст в виде 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