Little Rubdary has been training a lot for the Mathematics and Informatics Olympiads. She has been studying divisibility, and has come with a new problem for you!

Is there a positive number that is divisible by the first N natural numbers? If so, can you find the smallest one?
Can you find the answer to Q values of N?

You gladly accept this challenge, but with one condition: as the answers may be extremely large, you will show them modulo some number M

Input

The first line contains two integer Q and M, which specify the number of questions to be answered and the modulo respectively. Then, will follow the descriptions of the Q questions.

Output

For each question you must print the answer to the challenge modulo M in a single line. In case there is no answer to the question, you must output -1

Example

Input:
5 990901
1
6
12
20
60
Output:
1
60
27720
921726
823252

Constraints

1 ≤ Q ≤ 10³
1 ≤ N ≤ 3*10⁵
2 ≤ M ≤ 10⁹