310943: CF1912D. Divisibility Test
Description
Daisy has recently learned divisibility rules for integers and she is fascinated by them. One of the tests she learned is a divisibility test by 3. You can find a sum of all digits of a decimal number and check if the resulting sum is divisible by 3. Moreover, the resulting sum of digits is congruent modulo 3 to the original number — the remainder modulo 3 is preserved. For example, $75 \equiv 7 + 5 \pmod 3$. Daisy is specifically interested in such remainder preserving divisibility tests.
There are more examples like that that she learned for decimal integers (integers base 10):
- To test divisibility modulo 11, find an alternating sum of digits. Counting digits from the last (least significant) digit, add digits on odd positions (the last, 3rd to the last, etc) and subtract digits on even positions (2nd to the last, 4th to the last, etc) to get the sum that is congruent modulo 11 to the original number. For example, $123 \equiv 1 - 2 + 3 \pmod {11}$.
- To test divisibility modulo 4, keep the last two digits. Their value is congruent modulo 4 to the original number. For example, $876543 \equiv 43 \pmod 4$.
- To test divisibility modulo 7, find an alternating sum of groups of three digits. For example, $4389328 \equiv 4 - 389 + 328 \pmod 7$.
Similar tests can be found in other bases. For example, to test divisibility modulo 5 for octal numbers (base 8), find an alternating sum of groups of two digits. For example, $1234_8 \equiv -12_8 + 34_8 \pmod 5$.
Daisy wants to find such rules for a given base $b$. She is interested in three kinds of divisibility rules:
- Kind 1 — take the last $k$ digits of an integer in base $b$.
- Kind 2 — take a sum of groups of $k$ digits of an integer in base $b$.
- Kind 3 — take an alternating sum of groups of $k$ digits of an integer in base $b$.
It is not always possible to find such a divisibility rule. For example, in base 10 there is no such test for divisibility modulo 6, even though different approaches to testing divisibility by 6 exist.
Given base $b$ and modulo $n$, Daisy wants to know the smallest group size $k$ for which such a divisibility test exits.
InputThere are several tests in the input. The first line of the input contains an integer $t$ — the number of tests. The next $t$ lines describe the tests.
Each test consists of a line with two integers $b$ and $n$ — the base and the modulo ($b, n \ge 2$). The sum of all $b$ values in the input does not exceed $10^6$, and the sum of all $n$ values in the input does not exceed $10^6$.
OutputWrite $t$ lines — a line for each test in the input. On a line for a test write a single integer $0$ if the divisibility test for a given $b$ and $n$ does not exist. Otherwise, write two integers $a$ and $k$, where $a$ is the kind of the divisibility test (1, 2, or 3) and $k$ is the number of digits in a group for the test, such that $k$ is the lowest among all possible divisiblity tests for the given $b$ and $n$.
ExampleInput6 10 3 10 11 10 4 10 7 8 5 10 6Output
2 1 3 1 1 2 3 3 3 2 0
Output
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 可除性的规则。
给定基数 $ b $ 和模 $ n $，Daisy 想要知道存在这样的可除性测试的最小组大小 $ k $。
输入输出数据格式：
输入：
- 输入包含多个测试。第一行包含一个整数 $ t $ —— 测试的数量。接下来的 $ t $ 行描述了测试。
- 每个测试由一行组成，包含两个整数 $ b $ 和 $ n $ —— 基数和模数（$ b, n \ge 2 $）。输入中所有 $ b $ 值的总和不超过 $ 10^6 $，所有 $ n $ 值的总和也不超过 $ 10^6 $。
输出：
- 对于输入中的每个测试，输出一行。对于每个测试，如果不存在给定 $ b $ 和 $ n $ 的可除性测试，则输出单个整数 0。否则，输出两个整数 $ a $ 和 $ k $，其中 $ a $ 是可除性测试的类型（1、2 或 3），$ k $ 是测试中数字组的数量，使得 $ k $ 是所有可能的给定 $ b $ 和 $ n $ 的可除性测试中最低的。题目大意： 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 可除性的规则。 给定基数 $ b $ 和模 $ n $，Daisy 想要知道存在这样的可除性测试的最小组大小 $ k $。 输入输出数据格式： 输入： - 输入包含多个测试。第一行包含一个整数 $ t $ —— 测试的数量。接下来的 $ t $ 行描述了测试。 - 每个测试由一行组成，包含两个整数 $ b $ 和 $ n $ —— 基数和模数（$ b, n \ge 2 $）。输入中所有 $ b $ 值的总和不超过 $ 10^6 $，所有 $ n $ 值的总和也不超过 $ 10^6 $。 输出： - 对于输入中的每个测试，输出一行。对于每个测试，如果不存在给定 $ b $ 和 $ n $ 的可除性测试，则输出单个整数 0。否则，输出两个整数 $ a $ 和 $ k $，其中 $ a $ 是可除性测试的类型（1、2 或 3），$ k $ 是测试中数字组的数量，使得 $ k $ 是所有可能的给定 $ b $ 和 $ n $ 的可除性测试中最低的。