60 is divisible by 2, 3, 4 and 5. No smaller number than 60 has this property.

Input

On the first line, you will be given two integers T (the number of test cases), and M (an integer).
Each of the next T lines contains an integer N.

Output

For each test case, output on one line, the smallest number that is divisible by all integers from 1 to N (inclusive).
As the answer may be a big number, output it modulo M.

Example

Input:
1 1000000007
5

Output:
60

Constraints

T <= 10^5

10^8 <= M <= 2×10^9, a prime number

0 < N < 10^8

Information

There's one easy input file, and several harder ones. Time limit allows unoptimized code with fast languages to get AC ; for slower languages it may be hard.
Good luck and have fun ;-)

Edit(2017-02-11) : New time limit (after compiler changes).