Bytelandia States Union (BSU) 有许多自然奇观！但最神秘的奇观无疑是 Murbeda 矩形。在这里，时间和空间的行为相当反常。尽管经过多年的研究，Bytelandia 的科学家们仍未找到这种异常现象发生的原因。幸运的是，他们已经理解了 Murbeda 矩形的物理运作方式。

将 Murbeda 矩形视为一个大矩形。科学家们将其划分为 $2 \cdot 10^9 \times 2 \cdot 10^9$ 个小方格。每个方格都有坐标 $(x, y)$，其中 $x$ 轴从北向南延伸，$y$ 轴从西向东延伸。因此，西北角的方格坐标为 $(1, 1)$，东南角的方格坐标为 $(2 \cdot 10^9, 2 \cdot 10^9)$。在方格 $(x_2, y_2)$ 处有一个传送门，这是连接 Murbeda 矩形与外界的唯一途径。

假设你位于矩形中的方格 $(x, y)$。你可以向四个方向（北、南、东、西）之一移动，从而使其中一个坐标增加或减少 1。你不能走出矩形范围：例如，你不能从方格 $(2 \cdot 10^9, 42)$ 向南移动，也不能从方格 $(42, 1)$ 向西移动。如果这样做，你可能会掉进充满毒蛇的深谷中。

最令人着迷的是在某个方向上移动所花费的时间。如果你位于方格 $(x, y)$，那么：

• 向南移动（$x$ 坐标增加 1）需要 $f_s(x, y) = 2xy^2 + 2y^2 + x^2$ 秒；
• 向北移动（$x$ 坐标减少 1）需要 $f_n(x, y) = -2xy^2 + 2y^2 + x^2$ 秒；
• 向东移动（$y$ 坐标增加 1）需要 $f_e(x, y) = 2x^2y + 2x^2 + y^2$ 秒；
• 向西移动（$y$ 坐标减少 1）需要 $f_w(x, y) = -2x^2y + 2x^2 + y^2$ 秒。

在方格之间移动所花费的时间甚至可能是负数！这个地方真的很特别。科学家们打算从 Murbeda 矩形中营救 $n$ 个人。对于站在方格 $(x_1, y_1)$ 的人，他们需要确定到达传送门所需的最短时间。可以证明，这种最短时间是存在的，因此没有人可以通过四处走动达到无限小的时间。由于这个地方极其特殊，这 $n$ 个人中的每一个人可能需要不同的传送门。

输入格式

第一行包含一个整数 $n$，表示需要营救的人数 ($1 \le n \le 5 \cdot 10^4$)。

接下来的 $n$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$，分别表示第 $i$ 个人的位置和他们对应的传送门位置 ($1 \le x_1, y_1, x_2, y_2 \le 10^9$)。

输出格式

输出 $n$ 行。第 $i$ 行应包含第 $i$ 个人到达其传送门所需的最短时间（以秒为单位）。由于这个数值可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

4
1 1 1 1
1 3 2 1
2 1 1 3
10 2 20 6

样例输出 1

0
12
17
16999