I. Bingo
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given two integers $$$n$$$, $$$m$$$ and an integer sequence $$$a_1, a_2, \cdots, a_{nm}$$$ of length $$$n \times m$$$, we're going to fill a grid of $$$n$$$ rows and $$$m$$$ columns with the integers from the sequence. More specifically, let $$$(i, j)$$$ be the cell on the $$$i$$$-th row and the $$$j$$$-th column, we'll put the $$$((i - 1) \times m + j)$$$-th element of the sequence (that is, $$$a_{(i - 1) \times m + j}$$$) into that cell.

We say an integer $$$k$$$ is a "bingo integer" of the sequence, if after filling all the cells, at least one of the two following conditions is satisfied.

  • There is at least one row, where all integers in the cells of that row are less than or equal to $$$k$$$.
  • There is at least one column, where all integers in the cells of that column are less than or equal to $$$k$$$.

It is easy to see that a sequence may have multiple bingo integers, however in this problem, we're only interested in the smallest bingo integer.

Calculate the sum of the smallest bingo integers for all $$$(nm)!$$$ permutations of the given sequence. As the answer may be large, output the answer modulo $$$998\,244\,353$$$.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \times 10^5$$$, $$$1 \le n \times m \le 2 \times 10^5$$$), indicating the number of rows and columns of the grid.

The second line contains $$$n \times m$$$ integers $$$a_1, a_2, \cdots, a_{nm}$$$ ($$$0 \le a_i \lt 998\,244\,353$$$) indicating the given sequence.

It's guaranteed that the sum of $$$n \times m$$$ of all test cases will not exceed $$$4 \times 10^5$$$.

Output

For each test case, output one line containing one integer indicating the answer.

Example
Input
4
2 2
1 3 2 4
3 1
10 10 10
1 3
20 10 30
3 4
1 1 4 5 1 4 1 9 1 9 8 10
Output
56
60
60
855346687
Note

For the first sample test case, if $$$1$$$ and $$$2$$$ are not on the same row or column, then the smallest bingo integer will be $$$3$$$, otherwise the smallest bingo integer will be $$$2$$$. There are $$$8$$$ permutations where $$$1$$$ and $$$2$$$ are not on the same row or column, so the answer is $$$8 \times 3 + (4! - 8) \times 2 = 56$$$.

For the second sample test case, the smallest bingo integer is always $$$10$$$, so the answer is $$$3! \times 10 = 60$$$.