题目描述

在数轴上有三个坐标不可区分的石头。考虑对这些石头进行以下操作：

• 将 $A, B, C$ 按照坐标的升序排列（相同坐标的情况下任意排列）。执行以下操作之一：
  • 将 $A$ 移动到与 $B$ 关于中心对称的位置。
  • 将 $C$ 移动到与 $B$ 关于中心对称的位置。

给定初始坐标 $a, b, c$。找出经过零次或多次操作后，三个石头的坐标可能的组合数量，并对 $998244353$ 取模。

请解决给定的 $T$ 个测试样例。

约束条件

• $1\leq T\leq 10^5$
• $\-10^{18}\leq a\leq b\leq c\leq 10^{18}$

输入格式

输入以以下格式从标准输入给出：

$T$ $\\text{case}_1$ $\\vdots$ $\\text{case}_T$

每个测试样例的格式为：

$a$ $b$ $c$

输出格式

打印 $T$ 行。第 $i$ 行应该包含 $\\text{case}_i$ 的答案。

样例输入 1

6
1 3 5
-2 -2 5
0 1 3
31 41 59
-123456789 0 987654321
-1000000000000000000 0 1000000000000000000

样例输出 1

5
2
9
70
182333351
5

对于 $(a,b,c) = (1,3,5)$，经过操作后的三个石头可能的组合有五种：

• $(1,3,5)$, $(1,1,3)$, $(-1,1,1)$, $(3,5,5)$, $(5,5,7)$。

下图可能会有所帮助。