给定整数 $A, B, C, D$。计算长度为 $A + B + C + D$ 的数组个数，满足：

• 数组中恰好包含 $A$ 个 $-2$，恰好 $B$ 个 $-1$，恰好 $C$ 个 $1$，恰好 $D$ 个 $2$。
• 数组中不存在和为 $0$ 的子数组。

由于该数量可能非常大，请输出其对 $998244353$ 取模的结果。

如果数组 $b$ 可以通过从数组 $c$ 的开头删除若干（可能为零或全部）元素，并从末尾删除若干（可能为零或全部）元素得到，则称 $b$ 是 $c$ 的子数组。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例仅一行，包含 4 个整数 $A, B, C, D$ ($0 \le A, B, C, D \le 10^6, A + B + C + D > 0$)。

输出格式

输出一个整数，即问题的答案。

样例

样例输入 1

5
69 0 0 0
1 1 1 1
0 0 3 3
6 1 0 6
10000 10000 1000000 1000000

样例输出 1

1
0
20
2
480402900

说明

在第一个测试用例中，仅存在一个这样的数组：由 69 个 $-2$ 组成的数组。

在第二个测试用例中，所有元素的和为 $(-2) + (-1) + 1 + 2 = 0$，因此不存在这样的数组。