I. Tearing Paper
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The English statement was translated by AI and may be slightly different from the original Chinese statement. Please refer to the Chinese statement if you have any questions.

Alice has a sheet of paper; some region on the paper contains important information, but the paper was torn into two pieces by Bob. Assuming the tear is random, Alice wants to know the probability that the important information is completely preserved in one of the two halves.

Formally:

There is an $$$n\times m$$$ sheet of paper on the plane, and the coordinate system partitions it into unit square grid cells. There is a "critical region" on the paper — a closed rectangle with vertices $$$(a,b)$$$, $$$(a,d)$$$, $$$(c,d)$$$, $$$(c,b)$$$, where

$$$$$$ 0 \leq a \lt c \leq n,\quad 0 \leq b \lt d \leq m. $$$$$$

Now Bob will tear the paper along a "legal path" from $$$(0,0)$$$ to $$$(n,m)$$$, and this path is chosen uniformly at random among all legal paths. A legal path means a lattice path from $$$(0,0)$$$ to $$$(n,m)$$$ where each step is either to the right (increase $$$x$$$ by $$$1$$$) or up (increase $$$y$$$ by $$$1$$$). Such a path necessarily divides the whole sheet into a "upper-left" part and a "lower-right" part. For convenience, a path that leaves one part empty is also considered legal.

We care whether the critical region is cut by this tearing path. If the entire closed rectangle of the critical region lies exactly on one side of the path (either entirely in the "upper-left" part or entirely in the "lower-right" part), we say the "critical region remains intact"; otherwise, it is considered cut by the tearing path.

We ask: among all possible legal paths, what is the probability that the "critical region remains intact"? Give the result modulo $$$998244353$$$ $$$^{\dagger}$$$.

$$$^{\dagger}$$$ Formally, let $$$M = 998\,244\,353$$$. It can be shown the answer can be expressed as a reduced fraction $$$\frac{p}{q}$$$ with integers $$$p,q$$$ and $$$q \not\equiv 0\pmod{M}$$$. Output the integer $$$p\cdot q^{-1}\bmod M$$$. In other words, output an integer $$$x$$$ with $$$0\le x \lt M$$$ such that $$$x\cdot q \equiv p \pmod{M}$$$.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 10^4$$$). The description of the test cases follows.

The first line of each test case contains six integers $$$n, m, a, b, c, d$$$ ($$$1 \leq n \leq 10^3, 1 \leq m \leq 10^6$$$, $$$0 \leq a \lt c \leq n$$$, $$$0 \leq b \lt d \leq m$$$), with meanings as described above.

Output

For each test case, output one integer on a separate line — the value of the probability that the "critical region remains intact" modulo $$$998244353$$$.

Example
Input
3
3 3 1 1 2 2
3 3 0 0 3 3
3 3 0 1 3 2
Output
1
299473306
199648871
Note

In the first sample test case, the critical region has size $$$1 \times 1$$$. It can never be split by any tearing path, so the probability that it remains intact is $$$1$$$.

In the second sample test case, the critical region has size $$$3 \times 3$$$, i.e. it is the entire sheet. Since the tearing path always divides the sheet into two nonempty parts unless one part is empty, the probability that the critical region remains intact is $$$\frac{2}{20}$$$, i.e. $$$\frac{1}{10}$$$.

In the third sample test case, the probability that the critical region remains intact is $$$\frac{8}{20}$$$, i.e. $$$\frac{2}{5}$$$.