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。

範例

輸入

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

輸出

2
3
994996658310742016
broken message
broken message