J. LCM Factorization
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For an integer $$$x$$$, define $$$f(x)$$$ as the sum of all distinct prime factors of $$$x$$$. For example, $$$f(60) = f(2^2 \cdot 3 \cdot 5) = 2 + 3 + 5 = 10$$$. In particular, $$$f(1) = 0$$$.

You are given a sequence of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ and an integer $$$k$$$. Find the sum, modulo $$$998\,244\,353$$$, of $$$f(\text{LCM}(a_{i_1}, a_{i_2}, \ldots, a_{i_k}))$$$ over all possible subsequences $$$1 \leq i_1 \lt i_2 \lt \cdots \lt i_k \leq n$$$ of length $$$k$$$.

Here, $$$\text{LCM}(a_{i_1}, a_{i_2}, \ldots, a_{i_k})$$$ denotes the least common multiple of the integers $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$. For example, $$$\text{LCM}(10, 20, 30) = 60$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 3 \cdot 10^5$$$) — the length of the sequence and the length of subsequences, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the elements of the sequence.

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

Output

For each test case, print a single integer — the answer modulo $$$998\,244\,353$$$.

Example
Input
3
4 2
2 1 3 4
3 3
2 2 2
1 1
1
Output
19
2
0
Note

In the first test case,

  • $$$f(\text{LCM}(a_1, a_2)) = f(\text{LCM}(2, 1)) = f(2) = 2$$$,
  • $$$f(\text{LCM}(a_1, a_3)) = f(\text{LCM}(2, 3)) = f(6) = 2 + 3 = 5$$$,
  • $$$f(\text{LCM}(a_1, a_4)) = f(\text{LCM}(2, 4)) = f(4) = 2$$$,
  • $$$f(\text{LCM}(a_2, a_3)) = f(\text{LCM}(1, 3)) = f(3) = 3$$$,
  • $$$f(\text{LCM}(a_2, a_4)) = f(\text{LCM}(1, 4)) = f(4) = 2$$$,
  • $$$f(\text{LCM}(a_3, a_4)) = f(\text{LCM}(3, 4)) = f(12) = 2 + 3 = 5$$$.

The sum of these values is $$$2 + 5 + 2 + 3 + 2 + 5 = 19$$$.