Background

CTT2021 D4T1.

Problem Description

Today, Xiao Q, who lives in a base-$14$ world, learned a method to determine whether a given big integer is a multiple of $9$. We use $(1BB40)_{14} = (70812)_{10}$ as an example to describe this method. Let $b=14$ and $p=9$. All operations in the method below are performed in base $b$.

1. From the least significant digit to the most significant digit, split the number into blocks, each consisting of $k=2$ consecutive digits. In the example, $(1BB40)_{b}$ is split into three blocks: $1 \mid BB \mid 40$.
2. From the least significant block to the most significant block, number each block starting from $0$. In the example, block $0$ is $40$, block $1$ is $BB$, and block $2$ is $1$.
3. Compute a value $b_i$ for block $i$: let the value of block $i$ in base $b$ be $a_i$. If $i$ is odd, then $b_i$ is the smallest non-negative integer such that $(a_i+b_i) \equiv 0 \pmod p$. If $i$ is even, then $b_i$ is the smallest non-negative integer such that $(a_i-b_i) \equiv 0 \pmod p$. In the example, $b_0=2$, $b_1=6$, and $b_2=1$.
4. Concatenate the $b_i$ values in order with larger indices in lower digits and smaller indices in higher digits, forming a base-$b$ number, and output it. In the example, the output is $(261)_{b} = (477)_{10}$. It is easy to verify that both $477$ and $70812$ are multiples of $p$.

It can be proven that the input and output numbers produced by the method above are either both multiples of $p$, or both not multiples of $p$. Also, the number of digits becomes smaller, so by repeating this process several times you can obtain a very small number, and then you can check it easily.

Xiao Q was deeply attracted by this algorithm, so he wants to give a general method for $b,p$ different from $14,9$. However, he found that when the values of $b,p$ change, $k$ in Step 1 is not necessarily $2$: sometimes it is $1$, sometimes it is greater than $2$, and sometimes there is no $k$ that satisfies the requirement at all. Therefore, for given $b$ and $p$, Xiao Q wants to know the minimum positive integer $k$ in Step 1 (in base $b$), such that no matter what the input is, the input and the corresponding output are either both multiples of $p$, or both not multiples of $p$, or report that such a $k$ does not exist.

Note that $p$ is not necessarily a prime number.

Input Format

There are multiple test cases in the testdata. It is guaranteed that within the same test point, $p$ is the same. The first line contains two positive integers $T,p$, with $1 \le T \le 10^5$ and $2 \leq p \le 10^{15}$, representing the number of test cases and the parameter $p$ of the method.

The next $T$ lines each contain one integer $b$, representing the base for each test case. It is guaranteed that $2 \leq p < b \leq 10 \times p$.

All numbers in the input are given in decimal.

Output Format

For each test case, output one line. If no valid $k$ exists, output -1; otherwise, output the minimum positive integer $k$ that satisfies the condition.

2 9
14
16

2
-1

Hint

For the physical and mental health of contestants, the distributed file provides a big-integer modular multiplication function mul(A, B, P) implemented in down.cpp. You need to ensure $A,B \in [0,P-1]$, and the function will return $(A \times B) \bmod P$. You may choose to use or not use this code freely. When calling it, you must ensure that $A,B,P$ are all no greater than $10^{15}$.

Translated by ChatGPT 5