Максимальное количество делителей
Помогите мистеру Стрэнджу решить следующую задачу: "Найдите максимальное количество положительных делителей всех целых чисел в интервале от 1 до и включая N (1 ≤ N ≤ 42^42)". Поскольку мистер Стрэндж не любит число P, вам нужно найти максимальное количество делителей только для чисел от 1 до N, которые не делятся на P.
Входные данные
Входной файл содержит несколько наборов данных. Ваша программа считывает количество наборов данных T (2 ≤ T ≤ 42), за которым следуют сами наборы данных. Каждый набор данных содержит ровно три строки. Первая строка содержит число P (которое не нравится мистеру Стрэнджу; 2 ≤ P_{ }≤ 1000000007). Вторая строка содержит число K (1 ≤ K_{ }≤ 42) интервалов [1, N], для которых нужно найти решение. Третья строка содержит K разделённых пробелами целых чисел, N_i, каждое в диапазоне 1 ≤ N_i_{ }≤ 42^42, представляющих верхнюю границу каждого интервала.
Выходные данные
Результат для каждого из T наборов данных должен быть записан в отдельных строках. Результаты для интервалов [1, N_i] должны быть разделены пробелами.
Объяснение. В каждом наборе данных вам предлагается найти максимальное количество делителей для чисел в интервалах [1, 8] и [1, 42]. Если мистеру Стрэнджу не нравится P=13, максимальное количество делителей равно 4 и достигается для чисел 6 (делители 1, 2, 3 и 6) и 8 (делители 1, 2, 4 и 8); максимальное количество делителей 9 достигается для числа 36. Если мистеру Стрэнджу не нравится P=6, числа 6, 12, 18, 24, 30, 36, 42 запрещены. Таким образом, то же максимальное 4 достигается только для числа 8; ни одно число в интервале [1, 42] не имеет 9 делителей, но максимальное количество 8 достигается для числа 40.