整除性判定规则

题目描述

除了直接进行除法之外，通常还可以通过一些规则判断一个数能否被另一个数整除。例如，在十进制中：

1. 如果一个数的最右边一位能被 $2$ 整除，那么这个数能被 $2$ 整除。例如，$42$、$38$ 和 $50$ 都能被 $2$ 整除。

2. 如果一个数的最右边两位组成的数能被 $4$ 整除，那么这个数能被 $4$ 整除。例如，$100$、$124$ 和 $1328$ 都能被 $4$ 整除。

3. 如果一个数的各位数字之和能被 $3$ 整除，那么这个数能被 $3$ 整除。例如，$123$ 能被 $3$ 整除，因为

   $$1+2+3=6=3\times 2.$$

   对 $9$ 也存在类似规则。

   判断一个数能否被 $99$ 整除时，可以从右向左每两位分成一组，并将所有分组对应的数相加。例如：

   $$2374310351037933$$

   能被 $99$ 整除，因为

   $$33+79+03+51+03+31+74+23=297=99\times 3.$$

4. 如果从右向左计算奇数位置数字之和与偶数位置数字之和的差，并且该差能被 $11$ 整除，那么原数能被 $11$ 整除。例如，$1270401$ 能被 $11$ 整除，因为

   $$1-0+4-0+7-2+1=11.$$

5. 判断一个数能否被 $7$ 整除时，可以从右向左每三位分成一组，再对这些分组交替加减。例如，$1668266767874$ 能被 $7$ 整除，因为

   $$874-767+266-668+001=-294=-42\times 7.$$

现在给定进制 $B$ 和除数 $D$，你需要自动寻找上述类型的整除性判定规则。

设一个 $B$ 进制整数从右向左每 $k$ 位分成一组，得到：

$$g_0,g_1,g_2,\ldots$$

其中 $g_0$ 是最右边的分组。需要寻找以下三类规则：

1. 最右端规则

如果一个数能否被 $D$ 整除，只取决于其最右边 $k$ 位组成的数，则输出：

Rightmost k

这类规则成立的条件等价于：

$$B^k\equiv 0\pmod D.$$

2. 分组求和规则

如果一个数能否被 $D$ 整除，可以通过判断

$$g_0+g_1+g_2+\cdots$$

能否被 $D$ 整除来确定，则输出：

Add all k

这类规则成立的条件等价于：

$$B^k\equiv 1\pmod D.$$

3. 分组交替加减规则

如果一个数能否被 $D$ 整除，可以通过判断

$$g_0-g_1+g_2-g_3+\cdots$$

能否被 $D$ 整除来确定，则输出：

Alternate k change sign

这类规则成立的条件等价于：

$$B^k\equiv -1\pmod D.$$

对于每一类规则，只考虑：

$$1\le k\le 1000.$$

如果同一类规则存在多个可行的 $k$，输出其中最小的 $k$。

如果能找到多类规则，应按照以下顺序输出：

1. Rightmost
2. Add all
3. Alternate

如果三类规则都不存在，则输出：

condition not found.

注意：这里只考虑上述单一规则，不考虑将多种规则组合使用。例如，在十进制中，分别利用 $2$ 和 $3$ 的整除规则可以判断一个数能否被 $6$ 整除，但这种复合规则不在本题考虑范围内。

输入格式

第一行包含一个整数 $N$，表示测试数据组数。

接下来 $N$ 行，每行包含两个整数 $B$ 和 $D$：

• $B$ 表示所使用的进制；
• $D$ 表示需要寻找整除规则的除数。

数据范围：

$$N\le 2000,$$ $$2<B<500,$$ $$2\le D<5000.$$

输出格式

对于每组测试数据，输出所有能够找到的规则。

同一组数据中的多类规则按照题目规定的顺序逐行输出。

如果没有找到任何规则，输出：

condition not found.

相邻两组测试数据的输出之间必须有一个空行。

输出中的英文、大小写及空格必须与题目要求完全一致。

样例输入

7
10 3
10 99
10 2
10 4
10 5
10 11
10 7

样例输出

Add all 1

Add all 2

Rightmost 1

Rightmost 2

Rightmost 1

Add all 2
Alternate 1 change sign

Add all 6
Alternate 3 change sign

@原题