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