Boom Bot

Raze is a new agent in Valorant Inc. Currently, she is training on how to use Boom Bot.

The training arena is an $N \times M$ grid where each cell has a height. We call a cell ground cell if its height is $1$.

The boom bot is placed on a cell in the grid. In each second, the bot can move to an adjacent cell whose height is not greater than the current cell. If there are multiple such cells, the bot picks a cell out of them randomly. If the bot reaches a ground cell, it blasts off immediately.

Raze has $Q$ queries to ask. She will place the bot on a cell and wants to know the expected time required for the boom bot to blast off.

Two cells are called adjacent if they share a side horizontally or vertically.

It is guaranteed that there will be at least one ground cell and no two ground cells will be adjacent.

Input

First line contains an integer $T (1 \leq T \leq 10)$, denoting the number of testcases.

In each testcase, the first line contains two integers $N (1 \leq N \leq 20)$ and $M (1 \leq M \leq 20)$, denoting the number of rows and columns in the grid respectively.

Each of the next $N$ lines contains $M$ integers, where each integer $H_{ij} (1 \leq H_{ij} \leq 2)$ denotes the height of the cell $(i, j)$.

Following line contains an integer $Q (1 \leq Q \leq N \times M)$, denoting the number of queries.

Each of the next $Q$ lines contains two integers $X (1 \leq X \leq N)$ and $Y (1 \leq Y \leq M)$, denoting the cell where the bot will be placed.

Subtask

• Subtask 1 (25 points): $N = 1$
• Subtask 2 (75 points): Original constraints

Output

For each query, you need to print the expected time required for the bot to blast off. The answer can be written in form $\frac{P}{Q}$ where $P$ and $Q$ are relatively prime integers and $Q \neq 0\mod 998244353 $.

Output the value of $P \times Q^{-1}$ modulo $998244353$.

Samples

1
1 3
1 2 2
3
1 1
1 2
1 3

0
3
4

1
2 2
2 2
2 1
3
1 1
1 2
2 2

4
3
0