Maximum Number of Divisors

Mr. Strange dislikes the number $P$, so you have to solve this problem for him.

Among the integers from $1$ to $N$, keep only the ones that are not divisible by $P$. Report the largest number of divisors any of the kept integers has.

Since $P \ge 2$, the number $1$ always survives, so the answer is at least $1$.

The first line contains the number of data sets $T$ ($2 \le T \le 100$).

Each data set consists of three lines. The first line contains the number $P$ ($2 \le P \le 10^9 + 7$) that Mr. Strange dislikes. The second line contains the number of intervals $K$ ($1 \le K \le 100$). The third line contains $K$ space separated integers $N_1, N_2, \dots, N_K$ ($1 \le N_i \le 4242$), where $N_i$ is the right end of the interval $[1, N_i]$.

Print one line per data set. Each line holds the $K$ answers for that data set in the order given, separated by single spaces. The $i$-th value is the largest number of divisors among the integers in $[1, N_i]$ that are not divisible by $P$.

With $P = 13$ and the interval $[1, 8]$, no multiple of $13$ is at most $8$. The numbers with the most divisors are $6$ (divisors $1, 2, 3, 6$) and $8$ (divisors $1, 2, 4, 8$), so the answer is $4$. Over $[1, 42]$ the number $36$ has $9$ divisors, which is the most.

With $P = 6$ the numbers $6, 12, 18, 24, 30, 36, 42$ are forbidden. Over $[1, 8]$ the maximum $4$ is now reached only by $8$. Over $[1, 42]$ no remaining number has $9$ divisors, so the answer is $8$, reached by $40$.