N. No Zero-Sum Subsegment
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given integers $$$A, B, C, D$$$. Count the number of arrays of length $$$A+B+C+D$$$, such that:

  • They contain exactly $$$A$$$ elements equal to $$$-2$$$, exactly $$$B$$$ elements equal to $$$-1$$$, exactly $$$C$$$ elements equal to $$$1$$$, exactly $$$D$$$ elements equal to $$$2$$$

  • They contain no subarray with sum equal to $$$0$$$.

As this number can be very large, output it modulo $$$998244353$$$.

An array $$$b$$$ is a subarray of an array $$$c$$$ if $$$b$$$ can be obtained from $$$c$$$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

The first line of the input contains a single integer $$$t$$$ $$$(1 \le t \le 10^5)$$$  — the number of test cases. The description of test cases follows.

The only line of each test case contains $$$4$$$ integers $$$A, B, C, D$$$ ($$$0 \le A, B, C, D \le 10^6$$$, $$$A+B+C+D \gt 0$$$).

Output

Output a single integer  — answer to the problem.

Example
Input
5
69 0 0 0
1 1 1 1
0 0 3 3
6 1 0 6
10000 10000 1000000 1000000
Output
1
0
20
2
480402900
Note

In the first test case, there exists only one such array: an array consisting of $$$69$$$ $$$-2$$$s.

In the second test case, the sum of all its elements is $$$(-2) + (-1) + 1 + 2 = 0$$$, so there are no such arrays.