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