Максимальна кількість дільників
Допоможіть містеру Стрейнджу вирішити таку задачу: "Знайти максимальну кількість додатних дільників серед усіх цілих чисел у діапазоні від 1 до включно N (1 ≤ N ≤ 42^42)". Оскільки це завдання для містера Стрейнджа, ситуація ускладнюється тим, що він не любить число P. Тому, вам потрібно знайти не фактичну максимальну кількість дільників усіх можливих чисел від 1 до N, а лише максимальну кількість дільників для чисел від 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.