F. 新取模运算
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

在这道题中，我们定义一个新的运算符号 $$$\oplus$$$ 并将其称为新取模运算。

当计算 $$$x \oplus y$$$ 时，如果 $$$x$$$ 不是 $$$y$$$ 的倍数，则得到 $$$x$$$ 除以 $$$y$$$ 的余数; 否则令 $$$x$$$ 不断除以 $$$y$$$ 直到 $$$x$$$ 不再是 $$$y$$$ 的倍数，假设它为 $$$x'$$$，然后得到 $$$x'$$$ 除以 $$$y$$$ 的余数。例如，$$$4\oplus 5=4$$$，$$$20\oplus 5=4$$$，$$$100\oplus 5=4$$$。

给定一个质数 $$$p$$$，接下来会有多组询问，对于每次询问会给出一个整数 $$$n$$$，你需要计算出 $$$n!\oplus p$$$ 的值。其中 $$$n!$$$ 是 $$$n$$$ 的阶乘，即所有小于等于 $$$n$$$ 的正整数的乘积。

Input

第一行包含两个整数 $$$T\ (1\le T\le 10^5)$$$ 和 $$$p\ (2\le p\le 10^6)$$$，分别表示询问的次数和给定的质数。

接下来 $$$T$$$ 行，每行包含一个整数 $$$n\ (1\le n\le 10^{18})$$$，含义如题目所述。

Output

对于每次询问，输出一行包含一个整数，即 $$$n\oplus p$$$ 的值。

Examples
Input
3 7
11
45
14
Output
4
1
2
Input
2 10007
1919
810
Output
3152
3679