Alice 设计了一个密码系统：它将明文编码为一个 64 位无符号整数 $x$，并随机选择一个 64 位无符号整数 $a$ 作为公钥，将明文加密得到密文 $b = a^x \bmod 2^{64}$。特别地，定义 $0^0 = 1$。

现在，Bob 截获了 $n$ 组加密信息 $(a_i, b_i)$ ($i = 1, 2, \dots, n$)。为了解密所有信息，Bob 需要对于每组加密信息，找到最小的整数 $x_i$ ($0 \le x_i < 2^{64}$)，使得 $a_i^{x_i} \equiv b_i \pmod{2^{64}}$，或者确定该信息已被损坏（即不存在满足条件的 $x_i$）。请编写一个程序帮助 Bob 完成这个任务。

输入格式

第一行包含一个整数 $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。

样例

输入样例 1

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

输出样例 1

2
3
994996658310742016
broken message
broken message