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 は各暗号化情報について $a_i^{x_i} \equiv b_i \pmod{2^{64}}$ を満たす最小の整数 $x_i$（$0 \le x_i < 2^{64}$）を求めるか、その情報が破損している（すなわち条件を満たす $x_i$ が存在しない）と判定する必要があります。Bob がこの作業を達成するのを助けるプログラムを作成してください。

入力

入力の 1 行目には、メッセージの個数を表す整数 $n$（$1 \le n \le 10^5$）が与えられます。

続く $n$ 行のうち $i$ 行目には、$i$ 番目の情報の公開鍵と暗号文をそれぞれ表す 2 つの整数 $a_i$ と $b_i$（$0 \le a_i, b_i < 2^{64}$）が与えられます。

出力

$n$ 行出力してください。$i$ 行目について：

• 問題文の条件を満たす $x_i$ が少なくとも 1 つ存在する場合は、そのうち最小のものを出力してください。
• そうでない場合は、broken message と 1 行に出力してください。

入出力例

入力

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

出力

2
3
994996658310742016
broken message
broken message