Help Mr. Strange to solve the following problem: "\textit{Find the maximum number of positive divisors of all integers in the interval from }\textbf{1}\textit{ up to and including} \textbf{N} (\textbf{1} ≤ \textbf{N}\textit{ }≤ \textbf{42^42})". Since it is Mr. Strange who solves the problem, the situation is complicated by the fact that he dislikes number \textbf{P}. Therefore, you should not find the actual maximum number of divisors of all possible numbers from \textbf{1} to \textbf{N}, but the maximum number of divisors only for numbers from \textbf{1} to \textbf{N}, which are not divisible by \textbf{P}. \InputFile The input file contains several data sets. Your program reads the number of data sets \textbf{T} (\textbf{2} ≤ \textbf{T}\textit{ }≤ \textbf{42}), followed by the actual data sets. Each data set contains exactly three lines. The first line contains the number \textbf{P} (which is disliked by Mr. Strange; \textbf{2} ≤ \textbf{P}\textit{_\{ \}}≤ \textbf{1000000007}). The second line contains the number\textit{ }\textbf{K} (\textbf{1} ≤ \textbf{K}\textit{_\{ \}}≤ \textbf{42}) of intervals \textbf{\[1, N\]} for which the solution is to be found. The third line contains \textbf{K} space-separated integers, \textbf{N_i}, each in the range \textbf{1} ≤ \textbf{N_i}\textit{_\{ \}}≤ \textbf{42^42} representing the upper limit of each interval. \OutputFile The result for each of the \textbf{T} data sets should be written on separate lines. The results for the intervals \textbf{\[1, N_i\]} should be space-separated. \textit{\textbf{Explanation}}. In each data set you are asked to find the maximal number of divisors for numbers in intervals \textbf{\[1, 8\]} and \textbf{\[1, 42\]}. If Mr. Strange dislikes \textbf{P=13}, the maximum number of divisors is \textbf{4} and is reached for the numbers \textbf{6} (divisors \textbf{1}, \textbf{2}, \textbf{3} and \textbf{6}) and \textbf{8} (divisors \textbf{1}, \textbf{2}, \textbf{4} and \textbf{8}); the maximum number of divisors \textbf{9} is reached for the number \textbf{36}. If Mr. Strange dislikes \textbf{P=6}, numbers \textbf{6}, \textbf{12}, \textbf{18}, \textbf{24}, \textbf{30}, \textbf{36}, \textbf{42} are prohibited. So, the same maximum \textbf{4} is reached only for the number \textbf{8}; no number in the interval \textbf{\[1, 42\]} has \textbf{9} divisors, but the maximum number \textbf{8} is reached for the number \textbf{40}.