Repovive

##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######

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

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

5G. Gift for AmShZ, Grid for Root

Constraints

Input

Output

Samples

Constraints