#P17920. Cipher

Cipher

Cipher

题目描述

给定 nn 对整数 (ai,bi)(a_i,b_i)。对每一对,求满足

aixi≡bi(mod264)a_i^{x_i}\equiv b_i\pmod{2^{64}}

的最小整数 xix_i,其中 0≤xi<2640\le x_i<2^{64}。如果不存在这样的整数,报告无解。规定 00=10^0=1。

输入格式

第一行一个整数 nn。

接下来 nn 行,每行两个十进制整数 ai,bia_i,b_i。

输出格式

输出 nn 行。第 ii 行输出对应的最小 xix_i;无解时输出 broken message。

数据范围

  • 1≤n≤1051\le n\le10^5。
  • 0≤ai,bi<2640\le a_i,b_i<2^{64}。

样例

5
2 4
3 27
1000000007 998244353
4 2
1000000007 1000000009
2
3
994996658310742016
broken message
broken message