eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Maximal Number of Divisors

Maximal Number of Divisors

Лимит времени 30 секунд
Лимит использования памяти 256 MiB

Help Mr. Strange to solve the following problem: "Find the maximum number of positive divisors of all integers in the interval from 1 up to and includingN (1N42^42)". Since it is Mr. Strange who solves the problem, the situation is complicated by the fact that he dislikes number P. Therefore, you should not find the actual maximum number of divisors of all possible numbers from 1 to N, but the maximum number of divisors only for numbers from 1 to N, which are not divisible by P.

Входные данные

The input file contains several data sets. Your program reads the number of data sets T (2T42), 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; 2P_{ }1000000007). The second line contains the numberK (1K_{ }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 1N_i_{ }42^42 representing the upper limit of each interval.

Выходные данные

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.

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.

Пример

Входные данные #1
2
13
2
8 42
6
2
8 42
Выходные данные #1
4 9
4 8
Источник ACM ICPC SEERC-2012, 13.10.2012 Bucharest, Vinnica