Today, Xiao Q, who lives in a base-$14$ world, learned a method to determine whether a given large number 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 following method are performed in base $b$.

1. Starting from the least significant digit, divide the number into segments of length $k=2$. In the example, $(1BB40)_{b}$ is divided into three segments: $1 \mid BB \mid 40$.
2. Number each segment starting from $0$ from the least significant to the most significant. In the example, segment $0$ is $40$, segment $1$ is $BB$, and segment $2$ is $1$.
3. For the $i$-th segment, calculate the value $b_i$: Let $a_i$ be the value of the $i$-th segment in base $b$. If $i$ is odd, $b_i$ is the smallest non-negative integer such that $(a_i+b_i) \equiv 0 \pmod{p}$. If $i$ is even, $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, b_2=1$.
4. Concatenate $b_i$ in order of decreasing index (highest index first, lowest index last) to form a base-$b$ number and output it. In the example, the result 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 of the above method are either both multiples of $p$ or both not multiples of $p$. Furthermore, the number of digits decreases, so repeating this process several times will result in a very small number, which can then be easily checked.

Xiao Q is deeply fascinated by this algorithm and wants to find a general method for different values of $b$ and $p$ other than $14$ and $9$. However, he discovered that when $b$ and $p$ change, $k$ is not necessarily equal to $2$: sometimes it is $1$, sometimes it is greater than $2$, and sometimes a $k$ satisfying the conditions does not exist. Therefore, for given $b$ and $p$, Xiao Q wants to know the minimum positive integer $k$ for the first step of the above method such that, regardless of the input, 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

The input is read from standard input.

There are multiple test cases in a single test file, and $p$ is guaranteed to be the same for all test cases within the same file. The first line contains two positive integers $T$ and $p$, representing the number of test cases and the parameter $p$ of the method, respectively.

Each of the following $T$ lines contains an integer $b$, representing the base for each test case.

All numbers in the input are given in decimal.

Output

For each test case, output a single line. If no valid $k$ exists, output -1. Otherwise, output the minimum positive integer $k$ that satisfies the condition.

Examples

Input 1

2 9
14
16

Output 1

2
-1

Constraints

For all data, it is guaranteed that $1 \le T \le 10^{5}$, $2 \leq p \le 10^{15}$, and $2 \leq p < b \leq 10 \times p$.

For the sake of the contestants' well-being, the provided down.cpp file implements a large integer modular multiplication function mul(A, B, P). You must ensure $A, B \in [0, P-1]$ and $P \leq 10^{15}$. The function returns $(A \times B) \bmod P$. You may choose to use or not use this code.