You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

在 $Oxy$ 坐标平面上，横坐标与纵坐标都是整数的点叫做整点，由任一个整点(x,y)到整点(x+1,y+1)或(x+1,y-1)的有向线段叫做一个T步。

由整点 $A$ 到整点 $B$ 的一条T路是指由若干个T步组成的起点为 $A$ 、终点为 $B$ 的有向折线。

给定两个整点 $A$ 和 $B$ ，求 $A$ 到 $B$ 的不经过x轴的T路的数量。答案对 $998244353$ 取模。

注意:这道题目可能包含较大的输入数据量。在 Python 中，标准的 input() 函数速度较慢，可能导致超时。

解决方案： 请在代码开头添加以下两行来加速输入读取：

import sys
input = sys.stdin.readline

Input Format

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数（$1 \le T \le 10^5$）。对于每组测试数据：

第一行输入四个整数 $X_A$，$Y_A$，$X_B$，$Y_B$ （$-10^5 \le X \le 10^5$ ，$-10^5 \le Y \le 10^5$），表示整点 $A$ 和整点 $B$ 。

Output Format

输出 $A$ 到 $B$ 的不经过x轴的T路的数量。

Sample

Input：

6
0 1 2 1
0 2 4 2
0 1 2 -1
0 1 3 1
0 0 2 2
0 1 6 3

Output：

1
5
0
0
0
9