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