# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Boom Bot

By fsshakkhor · Limits 2s, 512 MB

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

InputOutput
1
1 3
1 2 2
3
1 1
1 2
1 3

0
3
4

InputOutput
1
2 2
2 2
2 1
3
1 1
1 2
2 2

4
3
0


### Statistics

86% Solution Ratio

NirjhorEarliest, 1M ago

MujahidFastest, 0.1s

NirjhorLightest, 786 kB

Deshi_TouristShortest, 2185B

### Submit
{"ft_lang_label":"__label__en","ft_lang_prob":0.87869745,"math_prob":0.994076,"size":1813,"snap":"2021-31-2021-39","text_gpt3_token_len":460,"char_repetition_ratio":0.12603648,"word_repetition_ratio":0.07848837,"special_character_ratio":0.23993382,"punctuation_ratio":0.10026385,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99621266,"pos_list":[0,1,2],"im_url_duplicate_count":[null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-09-21T11:55:33Z\",\"WARC-Record-ID\":\"<urn:uuid:c3f596d9-7ade-49d6-b752-ae06aaf20066>\",\"Content-Length\":\"53309\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:51bbbd48-54c2-4945-9881-c5a29682fd42>\",\"WARC-Concurrent-To\":\"<urn:uuid:fb7e6bb2-8d10-4502-99d9-c919cce807ce>\",\"WARC-IP-Address\":\"172.104.160.52\",\"WARC-Target-URI\":\"https://toph.co/p/boom-bot\",\"WARC-Payload-Digest\":\"sha1:GFJXOAHOMWHNFJ4DVLPGWX4LH27BIFSG\",\"WARC-Block-Digest\":\"sha1:IVJXWOLUC54GSOCGKKAUYS5LEOK3JFN6\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-39/CC-MAIN-2021-39_segments_1631780057202.68_warc_CC-MAIN-20210921101319-20210921131319-00716.warc.gz\"}"}