题目描述

国际象棋的王棋可以往其邻近的上下左右，左上，右上，左下，右下移动 1 格。在从 $(0,0)$ 到坐标 $(10^{100},10^{100})$ 的棋盘上，“王”希望从格点 $A$ 移动到格点 $B$，求最短可以到达 $B$ 的方案数。

由于方案种类较多，答案请对 $998244353$ 取模后输出。

输入描述

第一行包含一个整数 $T$（$1 \le T \le 10$），表示测试数据组数。

接下来 $T$ 行，每行包含 4 个空格隔开的整数 $x_1, y_1, x_2, y_2$，表示王棋所在位置 $(x_1, y_1)$ 和目标位置 $(x_2, y_2)$，满足 $0 \le x_1, y_1, x_2, y_2 \le 2 \times 10^5$。

输出描述

输出共 $T$ 行，每行输出一个整数，表示王棋从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的最短路方案数，对 $998244353$ 取模后的结果。

样例

3
2 3 4 3
1 4 4 6
114 514 1919 810

3
3
231613418

注释

样例中第一组测试用例，王棋从 $(2,3)$ 到 $(4,3)$，最短路径长度为 2，共有 3 种方案。

（原题配有图示，此处省略）