Максимальна кількість дільників#3846

Максимальна кількість дільників

30 секунд

256 мегабайтів

Легка

Допоможіть містеру Стрейнджу вирішити таку задачу: Знайти максимальну кількість додатних дільників серед усіх цілих чисел у діапазоні від $1$ до включно $N$ $(1 \leq N \leq 4 2^{42})$ (1 \leq N \leq 42^{42}). Оскільки це завдання для містера Стрейнджа, ситуація ускладнюється тим, що він не любить число $P$ . Тому, вам потрібно знайти не фактичну максимальну кількість дільників усіх можливих чисел від $1$ до $N$ , а лише максимальну кількість дільників для чисел від $1$ до $N$ , які не діляться на $P$ .

Вхідні дані

Вхідний файл містить кілька наборів даних. Ваша програма читає кількість наборів даних $T$ $(2 \leq T \leq 42)$ (2 \leq T \leq 42), за якими йдуть самі набори даних. Кожен набір даних містить рівно три рядки. Перший рядок містить число $P$ (яке не любить містер Стрейндж; $2 \leq P \leq 1000000007$ 2 \leq P \leq 1000000007). Другий рядок містить число $K$ $(1 \leq K \leq 42)$ (1 \leq K \leq 42) інтервалів $[1, N]$ для яких потрібно знайти відповідь. Третій рядок містить $K$ розділених пробілами цілих чисел, $N_{i}$ N_i, кожне в діапазоні $1 \leq N_{i} \leq 4 2^{42}$ 1 \leq N_i \leq 42^{42}, що представляють верхню межу кожного інтервалу.

Вихідні дані

Результат для кожного з $T$ наборів даних має бути записаний на окремих рядках. Результати для інтервалів $[1, N_{i}]$ [1, N_i] мають бути розділені пробілами.

Приклади

Приклад 1

Примітка

Пояснення. У кожному наборі даних вас просять знайти максимальну кількість дільників для чисел в інтервалах $[1, 8]$ та $[1, 42]$ . Якщо містер Стрейндж не любить $P = 13$ P = 13, максимальна кількість дільників дорівнює $4$ і досягається для чисел $6$ (дільники $1$ , $2$ , $3$ та $6$ ) і $8$ (дільники $1$ , $2$ , $4$ та $8$ ); максимальна кількість $9$ досягається для числа $36$ . Якщо містер Стрейндж не любить $P = 6$ P = 6, числа $6$ , $12$ , $18$ , $24$ , $30$ , $36$ , $42$ заборонені. Таким чином, та ж максимальна $4$ досягається лише для числа $8$ ; жодне число в інтервалі $[1, 42]$ не має $9$ дільників, але максимальна кількість $8$ досягається для числа $40$ .