Problem Description

In this problem, we define a new operator $\oplus$, called the new modulo operation.

When computing $x \oplus y$, if $x$ is not a multiple of $y$, the result is the remainder of $x$ divided by $y$. Otherwise, keep dividing $x$ by $y$ until $x$ is no longer a multiple of $y$. Let it be $x'$, and then take the remainder of $x'$ divided by $y$. For example, $4\oplus 5=4$, $20\oplus 5=4$, $100\oplus 5=4$.

Given a prime $p$, there are multiple queries. In each query, an integer $n$ is given, and you need to compute the value of $n!\oplus p$. Here, $n!$ is the factorial of $n$, i.e. the product of all positive integers less than or equal to $n$.

Input Format

The first line contains two integers $T\ (1\le T\le 10^5)$ and $p\ (2\le p\le 10^6)$, representing the number of queries and the given prime.

The next $T$ lines each contain an integer $n\ (1\le n\le 10^{18})$, with the meaning as described above.

Output Format

For each query, output one line containing one integer, the value of $n!\oplus p$.

3 7
11
45
14

4
1
2

2 10007
1919
810

3152
3679

Hint

Translated by ChatGPT 5