P12435 [NERC2023] 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. **类型 1** —— 取基数为 $b$ 的整数的最后 $k$ 位数字。 2. **类型 2** —— 取基数为 $b$ 的整数的 $k$ 位数字组的和。 3. **类型 3** —— 取基数为 $b$ 的整数的 $k$ 位数字组的交错和。 并非总能找到这样的可除性测试。例如，在基数为 10 时，没有针对模 6 的测试（尽管存在其他测试 6 的整除性的方法）。 给定基数 $b$ 和模数 $n$，Daisy 想知道是否存在这样的可除性测试，以及最小的组大小 $k$ 是多少。

输入包含多个测试用例。第一行是一个整数 $t$ —— 测试用例的数量。接下来的 $t$ 行描述每个测试用例。 每个测试用例包含一行两个整数 $b$ 和 $n$ —— 基数和模数（$b, n \ge 2$）。输入中所有 $b$ 的总和不超过 $10^6$，所有 $n$ 的总和不超过 $10^6$。

输出 $t$ 行 —— 每个测试用例一行。如果对于给定的 $b$ 和 $n$ 不存在可除性测试，则输出 `0`。否则，输出两个整数 $a$ 和 $k$，其中 $a$ 是可除性测试的类型（1、2 或 3），$k$ 是测试中数字组的位数，且 $k$ 是所有可能的测试中最小的。

翻译由 DeepSeek V3 完成