Операції над масивами#12384

Умова Розбір Обговорення

Операції над масивами

2 секунди

256 мегабайтів

Складна

Вам дано ціле число масив $a$ довжини $n$ .

Ви можете виконати не більше $k$ операцій наступного типу:

Виберіть індекс $i$ (1 \le i \le n).
Виберіть будь-який простий дільник $p$ числа a_i.
Замініть a_i на \dfrac{a_i}{p}.

Ваше завдання — визначити кількість різних масивів, які можна отримати після виконання не більше $k$ таких операцій.

Два масиви вважаються різними, якщо існує хоча б один індекс $i$ , для якого їх значення в цьому індексі відрізняються.

Примітка

Кожна операція змінює точно один елемент, ділячи його на один з його простих дільників.
Один і той же індекс може бути вибраний кілька разів, якщо операція залишається дійсною.

Вхідні дані

Перший рядок містить ціле число $t$ (1 \le t \le 10^4) — кількість наборів входних даних.

Кожен набір входних даних складається з двох рядків.

Перший рядок містить два цілі числа $n$ і $k$ (1 \le n,k \le 1000).

Другий рядок містить $n$ цілих чисел a_1, a_2, \ldots, a_n (1 \le a_i \le 10^6).

Гарантується, що сума n \cdot k для всіх наборів входних даних не перевищує 10^6.

Вихідні дані

Для кожного набору входних даних,

Виведіть кількість різних масивів, які можна отримати після виконання не більше $k$ операцій по модулю $998244353$ .

Приклади

Приклад 1

Loading

Loading

Оцінювання

Підзадача $1$ ( $20$ балів): (k = 1)
Підзадача $2$ ( $20$ балів): (a_i \text{ просте})
Підзадача $3$ ( $30$ балів): (a_i \text{ має вигляд } p \cdot q,\ \text{де } p \text{ і } q \text{ прості})
Підзадача $4$ ( $30$ балів): (a_i \le 100)
Підзадача $5$ ( $200$ балів): Без додаткових обмежень

(1 \leq i \leq n)

a_{i}

a_{i}

\frac{a _{i}}{p}

(1 \leq t \leq 1 0^{4})

(1 \leq n, k \leq 1000)

a_{1}, a_{2}, \dots, a_{n}

(1 \leq a_{i} \leq 1 0^{6})

n \cdot k

1 0^{6}

(k = 1)

(a_{i} просте)

(a_{i} має вигляд p \cdot q, де p і q прості)

(a_{i} \leq 100)