G. LCM Matrix
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There exist two unknown sequences of positive integers $$$r_1,\ldots,r_n$$$ and $$$c_1,\ldots,c_m$$$. They define an $$$n\times m$$$ matrix $$$A$$$ by $$$$$$A_{ij} = \operatorname{lcm}(r_i, c_j)$$$$$$ for every $$$1\le i\le n$$$ and $$$1\le j\le m$$$.

Some entries of this matrix were lost. You are given an $$$n\times m$$$ table $$$b$$$. If $$$b_{ij}=0$$$, then the entry $$$A_{ij}$$$ is lost. Otherwise, it is known that $$$A_{ij}=b_{ij}$$$.

Among all pairs of sequences $$$(r_1,\ldots,r_n)$$$ and $$$(c_1,\ldots,c_m)$$$ consistent with all nonzero entries of $$$b$$$, minimize the product $$$$$$r_1 \times r_2\times \cdots\times r_n \times c_1 \times c_2\times \cdots \times c_m.$$$$$$

Since the answer may be very large, output it modulo $$$998244353$$$.

It is guaranteed that the given table is valid, i.e. at least one such pair of sequences always exists.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 500$$$) — the dimensions of the matrix.

Then $$$n$$$ lines follow. The $$$i$$$-th of them contains $$$m$$$ integers $$$b_{i1},b_{i2},\ldots,b_{im}$$$ ($$$0\le b_{ij}\le 10^8$$$). If $$$b_{ij}=0$$$, then the entry $$$A_{ij}$$$ is lost. Otherwise, it is known that $$$A_{ij}=b_{ij}$$$.

It is guaranteed that there exists at least one pair of positive-integer sequences $$$(r_1,\ldots,r_n)$$$ and $$$(c_1,\ldots,c_m)$$$ whose LCM matrix matches all nonzero entries of $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$500$$$.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$500$$$.

Output

For each test case, output a single integer — the minimum possible value of $$$$$$r_1 \times r_2\times \cdots\times r_n \times c_1 \times c_2\times \cdots \times c_m.$$$$$$taken modulo $$$998244353$$$.

Example
Input
3
1 2
6 10
2 2
6 6
6 6
3 3
0 0 0
0 0 0
0 0 0
Output
30
36
1