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$$$.

Input

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$$$.

Output

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

Note

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$$$.

Omega Numbers

Examples