Алиса шифрлау жүйесін ойлап тапты: ол ашық мәтінді 64-биттік таңбасыз бүтін сан $x$ ретінде кодтайды және ашық кілт ретінде кездейсоқ 64-биттік таңбасыз бүтін сан $a$-ны таңдап, ашық мәтінді шифрлау арқылы $b = a^x \bmod 2^{64}$ шифрмәтінін алады. Дербес жағдайда, $0^0 = 1$ деп анықталады.

Енді Боб шифрланған ақпараттың $n$ жиынын $(a_i, b_i)$ ($i = 1, 2, \dots, n$) ұстап алды. Барлық ақпараттың шифрын ашу үшін Бобқа әрбір шифрланған ақпарат жиыны үшін $a_i^{x_i} \equiv b_i \pmod{2^{64}}$ шартын қанағаттандыратын ең кіші бүтін $x_i$ ($0 \le x_i < 2^{64}$) санын табу керек немесе ақпараттың бүлінгенін (яғни шартты қанағаттандыратын $x_i$ жоқ екенін) анықтау керек. Бобқа осы тапсырманы орындауға көмектесетін бағдарлама жазыңыз.

Кіріс деректер

Кіріс деректердің бірінші жолында хабарламалар санын білдіретін бір бүтін сан $n$ ($1 \le n \le 10^5$) берілген.

Келесі $n$ жолдың $i$-ші жолында $i$-ші ақпарат жиынының ашық кілті мен шифрмәтінін білдіретін екі бүтін сан $a_i$ және $b_i$ ($0 \le a_i, b_i < 2^{64}$) берілген.

Шығыс деректер

$n$ жол шығарыңыз, $i$-ші жол үшін:

• Егер есептің шарттарын қанағаттандыратын кемінде бір $x_i$ табылса, олардың ең кішісін шығарыңыз;
• Әйтпесе, broken message жолын шығарыңыз.

Мысал

Кіріс деректер

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009

Шығыс деректер

2
3
994996658310742016
broken message
broken message