今天,生活在 14 进制世界的小 Q 学习了一种判断给定的大数是否是 9 的倍数的方法。我们以 (1BB40)14=(70812)10 作为例子描述该方法,下面设 b=14,p=9,下面的方法中所有的运算在 b 进制下进行。
- 从低位往高位,将每个连续的 k=2 位划分为一段。例子中,(1BB40)b 被划分为 1∣BB∣40 三段。
- 从低位往高位从 0 开始给每一段编号。例子中,第 0 段为 40,第 1 段为 BB,第 2 段为 1。
- 对于第 i 段计算出值 bi:设第 i 段在 b 进制下的值为 ai,如果 i 为奇数则 bi 为满足 (ai+bi)≡0(mod 的最小非负整数 b_i,如果 i 为偶数则 b_i 为满足 (a_i-b_i) \equiv 0(\bmod\ p) 的最小非负整数 b_i。例子中有 b_0=2,b_1=6,b_2=1。
- 将 b_i 按照下标大的在低位,下标小的在高位的顺序顺次拼接,形成一个 b 进制数并输出。例子中输出结果为 (261)_{b} = (477)_{10}。容易验证 477 和 70812 都是 p 的倍数。
可以证明上述方法输入和输出的数要么同时是 p 的倍数,要么同时不是 p 的倍数。而且数字的位数变少了,所以多做几次就可以得到一个很小的数,然后就可以简单地判断了。
小 Q 深深地被这个算法吸引了,所以他想给出一个 b,p 不同于 14,9 时的通用方法。但是他发现,当上面的方法中 b,p 的取值变化时,k 不一定等于 2:有时会是 1,有时会大于 2,有时甚至不存在满足条件的 k。所以对于给定的 b,p,小 Q 想知道在 b 进制下上述方法的第一步中正整数 k 的最小值,使得无论输入如何,输入和对应的输出要么同时是 p 的倍数,要么同时不是 p 的倍数,或者报告这样的 k 不存在。
注意 p 不一定是质数。
输入格式
从标准输入读入数据。
测试点有多组测试数据,保证同一测试点下的 p 相同。输入的第一行包含两个正整数 T,p,分别表示该组测试点的测试数据组数与方法的 p 参数。
接下来 T 行每行输入一行一个整数 b 表示每组测试数据的进制。
输入中的所有数字按照十进制给出。
输出格式
输出到标准输出。
对于每组数据输出一行,若不存在合法的 k 输出 -1
,否则输出最小的满足条件的正整数 k。
样例
input
2 9 14 16
output
2 -1
数据范围与提示
对于所有数据,保证 1 \le T \le 10^{5},2 \leq p \le 10^{15},2 \leq p < b \leq 10 \times p。
子任务编号 | 2 \leq p \leq | 1 \leq T \leq | 分值 |
---|---|---|---|
1 | 3 | 10 | 5 |
2 | 10 | 5 | |
3 | 10^{2} | 10^{2} | 5 |
4 | 10^{4} | 11 | |
5 | 10^{6} | 11 | |
6 | 10^{8} | 10^{3} | 11 |
7 | 10^{10} | 11 | |
8 | 10^{12} | 7 | |
9 | 10^{14} | 10^{4} | 17 |
10 | 10^{15} | 10^{5} | 17 |
为了选手们的身心健康,下发文件中的 down.cpp
中实现了大整数取模乘法函数 mul(A, B, P)
,你需要保证 A,B \in [0,P-1],P\leq 10^{15},函数会返回 (A \times B) \bmod P。你可以自由选择使用或者不使用这份代码。