Gift for AmShZ, Grid for Root - Repovive Goodbye 2025 Round | Repovive

1G. Gift for AmShZ, Grid for Root

3500 pts5s256 MB

Root wanted to buy a nice New Year gift for AmShZ. Unfortunately, Hamed stole all of Root’s money! Root wished that Santa would bring him some money, but Hamed managed to steal Santa’s money as well! So, Root asked Santacci for help. Santacci appears only in emergencies and is famous for giving extremely large gifts.

This time, Santacci gave Root an $n \times m$ grid of integers.

A path is a sequence of cells that starts at $(1,1)$ and ends at $(n,m)$ . In each step, the path moves either one cell to the right or one cell down.

Each path visits exactly $n+m-1$ cells and defines a sequence of values written in the visited cells. For a fixed path, define its score as follows:

For every unordered pair of positions on the path, let $x$ and $y$ be the values at those positions.
If $x \times y$ is a perfect square, add $fib(\sqrt{x \times y})$ to the score.
Otherwise, add $0$ .

The Fibonacci function is defined as:

$fib(0)=0$
$fib(1)=1$
$fib(z)=fib(z-1)+fib(z-2)$ for $z \ge 2$

The value of the grid is defined as the sum of scores over all $\binom{n+m-2}{n-1}$ valid paths.

Root is too tired to compute this value by himself and wants to know how much money he can get from Santacci’s gift in order to buy a proper New Year present for AmShZ.

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

Constraints

$1 \le t \le 10^4$
$1 \le n, m \le 300$
$1 \le a_{i,j} \le 10^5$
The sum of $n \times m$ over all test cases not exceed $300^2$ .

Input

t \\[0.5em] \left. \begin{array}{l} n \quad m \\ a_{1,1} \quad a_{1,2} \quad \cdots \quad a_{1,m} \\ a_{2,1} \quad a_{2,2} \quad \cdots \quad a_{2,m} \\ \vdots \\ a_{n,1} \quad a_{n,2} \quad \cdots \quad a_{n,m} \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Explanation

In the second case, the product of the values in any two cells is not a perfect square, so the score of all paths is $0$ .

Output

166
0

This time, Santacci gave Root an $n \times m$ grid of integers.

A path is a sequence of cells that starts at $(1,1)$ and ends at $(n,m)$ . In each step, the path moves either one cell to the right or one cell down.

Each path visits exactly $n+m-1$ cells and defines a sequence of values written in the visited cells. For a fixed path, define its score as follows:

The Fibonacci function is defined as:

$fib(0)=0$
$fib(1)=1$
$fib(z)=fib(z-1)+fib(z-2)$ for $z \ge 2$

The value of the grid is defined as the sum of scores over all $\binom{n+m-2}{n-1}$ valid paths.

Root is too tired to compute this value by himself and wants to know how much money he can get from Santacci’s gift in order to buy a proper New Year present for AmShZ.

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

Constraints

$1 \le t \le 10^4$
$1 \le n, m \le 300$
$1 \le a_{i,j} \le 10^5$
The sum of $n \times m$ over all test cases not exceed $300^2$ .

t \\[0.5em] \left. \begin{array}{l} n \quad m \\ a_{1,1} \quad a_{1,2} \quad \cdots \quad a_{1,m} \\ a_{2,1} \quad a_{2,2} \quad \cdots \quad a_{2,m} \\ \vdots \\ a_{n,1} \quad a_{n,2} \quad \cdots \quad a_{n,m} \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

In the second case, the product of the values in any two cells is not a perfect square, so the score of all paths is $0$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

1G. Gift for AmShZ, Grid for Root

Input

Output

Samples

1G. Gift for AmShZ, Grid for Root

Constraints

Input

Output

Samples

Constraints