약수가 가장 많은 수

스트레인지 씨는 수 $P$를 싫어한다. 그래서 다음 문제를 대신 풀어 주어야 한다.

$1$ 이상 $N$ 이하의 정수 중에서 $P$로 나누어떨어지지 않는 수만 고른다. 그렇게 고른 수의 약수의 개수 중 최댓값을 구한다.

$P \ge 2$이므로 $1$은 언제나 후보로 남고, 답은 항상 $1$ 이상이다.

첫 줄에 데이터 세트의 개수 $T$ ($2 \le T \le 100$)가 주어진다.

각 데이터 세트는 세 줄로 이루어진다. 첫 줄에는 스트레인지 씨가 싫어하는 수 $P$ ($2 \le P \le 10^9 + 7$)가 주어진다. 둘째 줄에는 구간의 개수 $K$ ($1 \le K \le 100$)가 주어진다. 셋째 줄에는 $K$개의 정수 $N_1, N_2, \dots, N_K$ ($1 \le N_i \le 4242$)가 공백으로 구분되어 주어지며, $N_i$는 구간 $[1, N_i]$의 오른쪽 끝이다.

데이터 세트마다 한 줄씩 출력한다. 각 줄에는 그 데이터 세트의 답 $K$개를 입력에 주어진 순서대로 공백으로 구분해 출력한다. $i$번째 값은 구간 $[1, N_i]$에 있으면서 $P$로 나누어떨어지지 않는 정수의 약수 개수 중 최댓값이다.

$P = 13$이고 구간이 $[1, 8]$이면 $8$ 이하에 $13$의 배수가 없다. 약수가 가장 많은 수는 $6$(약수 $1, 2, 3, 6$)과 $8$(약수 $1, 2, 4, 8$)이고 개수는 $4$다. 구간 $[1, 42]$에서는 $36$의 약수가 $9$개로 가장 많다.

$P = 6$이면 $6, 12, 18, 24, 30, 36, 42$가 후보에서 빠진다. 구간 $[1, 8]$에서는 최댓값 $4$가 $8$에서만 나온다. 구간 $[1, 42]$에는 약수가 $9$개인 수가 남지 않으므로, 약수가 $8$개인 $40$이 답이 된다.