F. оМега числа
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для заданного числа $$$n$$$ рассмотрим функцию $$$\omega(n)$$$, которая равна количеству уникальных простых чисел в разложении числа $$$n$$$ на простые множители.

Например, $$$\omega (12) = \omega (2^2 \cdot 3) = 2$$$. А $$$\omega (120) = \omega (2^3 \cdot 3 \cdot 5) = 3$$$.

Для массива натуральных чисел $$$a$$$ и натурального числа $$$k$$$ определим $$$\operatorname{f}(a, k) = \sum_{i \lt j} \omega(a_i \cdot a_j)^k$$$ по всем $$$i \lt j$$$.

Дан массив натуральных чисел $$$a$$$ длины $$$n$$$ и натуральное число $$$k$$$. Посчитайте $$$\operatorname{f}(a, k)$$$ по модулю $$$998\,244\,353$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит 2 целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$$$) — длину массива $$$a$$$ и степень операции соответственно.

Вторая строка каждого набора входных данных содержит $$$n$$$ натуральных чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — массив $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите в единственной строке целое число — значение функции $$$\operatorname{f}(a, k)$$$ по модулю $$$998\,244\,353$$$.

Пример
Входные данные
3
4 1
3 3 3 3
4 1
1 1 1 1
4 2
1 2 3 4
Выходные данные
6
0
12
Примечание

Объяснение первого набора тестовых данных примера:

Для любой пары ($$$i,j$$$), значение $$$\omega(x)$$$ для произведения равно $$$\omega(3^2) = 1$$$. Всего пар $$$6$$$, а степень равна $$$1$$$. Итоговый ответ $$$6$$$.

Объяснение второго набора тестовых данных примера:

В любой паре второго набора данных произведение чисел пары равно $$$1$$$, соответственно количество простых в нем равно $$$0$$$. Поэтому итоговый ответ также равен $$$0$$$.

Объяснение третьего набора тестовых данных примера:

Рассмотрим все пары ($$$i,j$$$):

  • ($$$1,2$$$): произведение чисел на позициях $$$1$$$ и $$$2$$$ равно $$$a_1 \cdot a_2 = 1 \cdot 2$$$, $$$\omega(2) = 1$$$.
  • ($$$1,3$$$): произведение чисел на позициях $$$1$$$ и $$$3$$$ равно $$$a_1 \cdot a_3 = 1 \cdot 3$$$, $$$\omega(3) = 1$$$.
  • ($$$1,4$$$): произведение чисел на позициях $$$1$$$ и $$$4$$$ равно $$$a_1 \cdot a_4 = 1 \cdot 4$$$, $$$\omega(2^2) = 1$$$.
  • ($$$2,3$$$): произведение чисел на позициях $$$2$$$ и $$$3$$$ равно $$$a_2 \cdot a_3 = 2 \cdot 3$$$, $$$\omega(2 \cdot 3) = 2$$$.
  • ($$$2,4$$$): произведение чисел на позициях $$$2$$$ и $$$4$$$ равно $$$a_2 \cdot a_4 = 2 \cdot 4$$$, $$$\omega(2^3) = 1$$$.
  • ($$$3,4$$$): произведение чисел на позициях $$$3$$$ и $$$4$$$ равно $$$a_3 \cdot a_4 = 3 \cdot 4$$$, $$$\omega(3 \cdot 2^2) = 2$$$.

В ответ значения $$$\omega(x)$$$ входят в степени $$$2$$$, поэтому $$$1^2 + 1^2 + 1^2 + 2^2 + 1^2 + 2^2 = 12$$$.