CF1912D.Divisibility Test

Daisy 最近学习了整数的整除规则，并对此产生了浓厚的兴趣。她学到的其中一个测试是关于 $3$ 的整除性。你可以将一个十进制数的所有数字相加，然后检查所得的和是否能被 $3$ 整除。此外，数字之和与原数在模 $3$ 意义下同余——即模 $3$ 的余数保持不变。例如，$75 \equiv 7 + 5 \pmod 3$。Daisy 对这种余数保持的整除性测试尤其感兴趣。

她还学到了更多类似的十进制（以 $10$ 为底的整数）整除性测试：

• 检查能否被 $11$ 整除时，计算数字的交错和。从最后一位（最低位）开始，奇数位（最后一位、倒数第三位等）上的数字相加，偶数位（倒数第二位、倒数第四位等）上的数字相减，得到的和与原数在模 $11$ 意义下同余。例如，$123 \equiv 1 - 2 + 3 \pmod{11}$。
• 检查能否被 $4$ 整除时，只需保留最后两位数字。它们的值与原数在模 $4$ 意义下同余。例如，$876543 \equiv 43 \pmod 4$。
• 检查能否被 $7$ 整除时，计算每组三位数字的交错和。例如，$4389328 \equiv 4 - 389 + 328 \pmod 7$。

在其他进制下也可以找到类似的测试方法。例如，对于八进制数（以 $8$ 为底），检查能否被 $5$ 整除时，计算每组两位数字的交错和。例如，$1234_8 \equiv -12_8 + 34_8 \pmod 5$。

Daisy 想要为给定的进制 $b$ 找到类似的规则。她对三种类型的整除性规则感兴趣：

• 类型 1 —— 取一个以 $b$ 为底的整数的最后 $k$ 位数字。
• 类型 2 —— 取一个以 $b$ 为底的整数，每 $k$ 位数字分为一组，对各组求和。
• 类型 3 —— 取一个以 $b$ 为底的整数，每 $k$ 位数字分为一组，对各组求交错和（正负交替相加）。

并非总能找到这样的整除性规则。例如，在十进制下，没有关于 $6$ 的这种测试，尽管存在其他测试 $6$ 的方法。

给定进制 $b$ 和模数 $n$，Daisy 想知道存在上述哪种类型的整除性测试，并且希望找到最小的分组大小 $k$。

输入包含若干组测试数据。第一行包含一个整数 $t$，表示测试组数。接下来的 $t$ 行，每行描述一组测试。

每组测试包含两个整数 $b$ 和 $n$，分别表示进制和模数（$b, n \ge 2$）。所有输入中 $b$ 的总和不超过 $10^6$，所有 $n$ 的总和也不超过 $10^6$。

输出 $t$ 行，每行对应输入中的一组测试。对于每组测试，若不存在对应的整除性测试，输出一个整数 $0$。否则，输出两个整数 $a$ 和 $k$，其中 $a$ 表示整除性测试的类型（1、2 或 3），$k$ 表示分组的位数，且 $k$ 是所有可能的整除性测试中最小的。

由 ChatGPT 4.1 翻译