For a given prime $P$, we define $S(x)$ as the sequence of length $P$ given by $\{x^0\bmod P, x^1\bmod P, \dots, x^{P-1}\bmod P\}$, and we define $T(x)$ as the prefix maximum sequence of $S(x)$, i.e., $T(x)[p] = \max_{i=1}^p S(x)[i]$.

Given $T$ test cases, for each input $x$, you need to calculate the sum of the elements in $T(x)$, without taking any modulo.

For example, when $P=5$, $S(2)=\{1,2,4,3,1\}$, $T(2)=\{1,2,4,4,4\}$, so the sum of the elements in $T(2)$ is $15$.

Please note the data generation method.

Input

The first line contains two positive integers $P$ and $T$, representing the modulus and the number of test cases.

The next $T$ lines each contain a positive integer $x$, representing a test case.

Output

$T$ lines, each containing the answer for the corresponding test case.

Examples

Input 1

233 3
1
3
33

Output 1

233
51426
53224

Constraints

Each subtask contains no more than 15 test cases, $T=200$, $P$ is chosen independently and uniformly at random from primes within the specified range, and each $x$ is generated independently and uniformly at random in $[1, P)$.

Subtask 1 (10pts): $P\in [900, 1000]$.

Subtask 2 (20pts): $P\in [0.9\times 10^7, 10^7]$.

Subtask 3 (30pts): $P\in [0.9\times 10^8, 10^8]$.

Subtask 4 (40pts): $P\in [0.9\times 10^9, 10^9]$.