CF1931G.One-Dimensional Puzzle

You have a one-dimensional puzzle, all the elements of which need to be put in one row, connecting with each other. All the puzzle elements are completely white and distinguishable from each other only if they have different shapes.

Each element has straight borders at the top and bottom, and on the left and right it has connections, each of which can be a protrusion or a recess. You cannot rotate the elements.

You can see that there are exactly $4$ types of elements. Two elements can be connected if the right connection of the left element is opposite to the left connection of the right element.

All possible types of elements.

The puzzle contains $c_1, c_2, c_3, c_4$ elements of each type. The puzzle is considered complete if you have managed to combine all elements into one long chain. You want to know how many ways this can be done.

你有一个一维拼图，其中所有拼图块都需要排成一行，并彼此连接。所有拼图块均为纯白色，仅当它们的形状不同时才能相互区分。

每个拼图块的顶部和底部边缘为直线，而左侧和右侧则具有连接结构，每个连接结构要么是凸起（protrusion），要么是凹陷（recess）。你不能旋转这些拼图块。

可以看出，拼图块恰好有 $4$ 种类型。两个拼图块可以连接，当且仅当左侧拼图块的右侧连接与右侧拼图块的左侧连接互为相反（即一凸一凹）。

所有可能的拼图块类型。

该拼图包含每种类型的拼图块数量分别为 $c_1, c_2, c_3, c_4$。若能将所有拼图块连接成一条长链，则称该拼图已完成。你想知道完成该拼图的方案数有多少种。

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

The description of each test case contains $4$ integers $c_i$ ($0 \le c_i \le 10^6$) — the number of elements of each type, respectively.

It is guaranteed that the sum of $c_i$ for all test cases does not exceed $4 \cdot 10^6$.

第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^5$）—— 表示输入测试用例的数量。随后是各测试用例的描述。

每个测试用例的描述包含 $4$ 个整数 $c_i$（$0 \le c_i \le 10^6$）—— 分别表示每种类型元素的个数。

保证所有测试用例中 $c_i$ 的总和不超过 $4 \cdot 10^6$。

For each test case, print one integer — the number of possible ways to solve the puzzle.

Two methods are considered different if there is $i$, such that the types of elements at the $i$ position in these methods differ.

Since the answer can be very large, output it modulo $998244353$.

If it is impossible to solve the puzzle, print $0$.

对于每个测试用例，输出一个整数——表示解决该谜题的可能方案数。

如果存在某个位置 $i$，使得两种方案中第 $i$ 个位置上的元素类型不同，则认为这两种方案是不同的。

由于答案可能非常大，请将结果对 $998244353$ 取模后输出。

如果无法解决该谜题，则输出 $0$。