CF2176F.Omega Numbers

For a given number $n$, consider the function $\omega(n)$, which is equal to the number of unique prime numbers in the prime factorization of the number $n$.

For example, $\omega (12) = \omega (2^2 \cdot 3) = 2$. And $\omega (120) = \omega (2^3 \cdot 3 \cdot 5) = 3$.

For an array of natural numbers $a$ and a natural number $k$, we define $\operatorname{f}(a, k) = \sum_{i \lt j} \omega(a_i \cdot a_j)^k$ for all $i \lt j$.

You are given an array of natural numbers $a$ of length $n$ and a natural number $k$. Calculate $\operatorname{f}(a, k)$ modulo $998\,244\,353$.

对于给定的正整数 $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$ 的下标对。

现给定一个长度为 $n$ 的正整数数组 $a$ 和一个正整数 $k$，请计算 $\operatorname{f}(a, k)$ 对 $998\,244\,353$ 取模的结果。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains 2 integers $n$ and $k$ ($1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$) —the length of the array $a$ and the exponent of the operation, respectively.

The second line of each test case contains $n$ natural numbers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$) —the array $a$.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $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$。

For each test case, output a single line containing an integer — the value of the function $\operatorname{f}(a, k)$ modulo $998\,244\,353$.

对于每个测试用例，输出一行，包含一个整数——函数 $\operatorname{f}(a, k)$ 对 $998\,244\,353$ 取模的结果。

Explanation of the first test case example:

For any pair ($i,j$), the value $\omega(x)$ for the product is $\omega(3^2) = 1$. There are a total of $6$ pairs, and the exponent is $1$. The final answer is $6$.

Explanation of the second test case example:

In any pair of the second test case, the product of the numbers in the pair equals $1$, so the number of primes in it is $0$. Therefore, the final answer is also $0$.

Explanation of the third test case example:

Consider all pairs ($i,j$):

• ($1,2$): the product of the numbers at positions $1$ and $2$ equals $a_1 \cdot a_2 = 1 \cdot 2$, $\omega(2) = 1$.
• ($1,3$): the product of the numbers at positions $1$ and $3$ equals $a_1 \cdot a_3 = 1 \cdot 3$, $\omega(3) = 1$.
• ($1,4$): the product of the numbers at positions $1$ and $4$ equals $a_1 \cdot a_4 = 1 \cdot 4$, $\omega(2^2) = 1$.
• ($2,3$): the product of the numbers at positions $2$ and $3$ equals $a_2 \cdot a_3 = 2 \cdot 3$, $\omega(2 \cdot 3) = 2$.
• ($2,4$): the product of the numbers at positions $2$ and $4$ equals $a_2 \cdot a_4 = 2 \cdot 4$, $\omega(2^3) = 1$.
• ($3,4$): the product of the numbers at positions $3$ and $4$ equals $a_3 \cdot a_4 = 3 \cdot 4$, $\omega(3 \cdot 2^2) = 2$.

In the answer, the values of $\omega(x)$ are raised to the power of $2$, so $1^2 + 1^2 + 1^2 + 2^2 + 1^2 + 2^2 = 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)$ 的值需平方后求和，即 $1^2 + 1^2 + 1^2 + 2^2 + 1^2 + 2^2 = 12$。