对于给定的数字 $$$n$$$,考虑函数 $$$\omega(n)$$$,它等于数字 $$$n$$$ 的素数分解中唯一素数的数量。
例如,$$$\omega (12) = \omega (2^2 \cdot 3) = 2$$$。并且 $$$\omega (120) = \omega (2^3 \cdot 3 \cdot 5) = 3$$$。
对于自然数数组 $$$a$$$ 和自然数 $$$k$$$,我们为所有 $$$i \lt j$$$ 定义 $$$\operatorname{f}(a, k) = \sum_{i \lt j} \omega(a_i \cdot a_j)^k$$$。
给你一个长度为 $$$n$$$ 的自然数数组 $$$a$$$ 和一个自然数 $$$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$$$ 的值。
示例
输入复制
34 13 3 3 34 11 1 1 14 21 2 3 4
输出复制
6012
注意
第一个测试用例示例说明:
对于任何对 ($$$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$$$。