Maximal Number of Divisors

Input

The input file contains several data sets. Your program reads the number of data sets $T$ (2 \leq T \leq 42), followed by the actual data sets. Each data set contains exactly three lines. The first line contains the number $P$ (which is disliked by Mr. Strange; 2 \leq P \leq 1000000007). The second line contains the number $K$ (1 \leq K \leq 42) of intervals $[1,N]$ for which the solution is to be found. The third line contains $K$ space-separated integers, N_i, each in the range 1 \leq N_i \leq 42^{42} representing the upper limit of each interval.

Output

The result for each of the $T$ data sets should be written on separate lines. The results for the intervals [1, N_i] should be space-separated.

Examples

Note

Explanation. In each data set you are asked to find the maximal number of divisors for numbers in intervals $[1,8]$ and $[1,42]$. If Mr. Strange dislikes P = 13, the maximum number of divisors is $4$ and is reached for the numbers $6$ (divisors $1$, $2$, $3$ and $6$) and $8$ (divisors $1$, $2$, $4$ and $8$); the maximum number of divisors $9$ is reached for the number $36$. If Mr. Strange dislikes P = 6, numbers $6$, $12$, $18$, $24$, $30$, $36$, $42$ are prohibited. So, the same maximum $4$ is reached only for the number $8$; no number in the interval $[1,42]$ has $9$ divisors, but the maximum number $8$ is reached for the number $40$.