問題文

互いに区別のできない $3$ つの石が、数直線上の座標が整数の点に置かれています。これらの石に対して次の操作を考えます：

• $3$ つの石を、その時点で座標の小さい方から順に（同じ位置にある石については適当な順に） $A, B, C$ とする。次のいずれかを行う。
  • $A$ を $B$ に関して対称な位置に移動する。
  • $C$ を $B$ に関して対称な位置に移動する。

はじめに $3$ つの石が置かれている座標 $a, b, c$ が与えられます。操作を何度でも行える（$0$ 回でもよい）とき、操作結果の $3$ つの石の座標の組合せとしてありうるものの個数を $998244353$ で割った余りを求めてください。

石が互いに区別できないことに注意してください。より厳密にいえば、$3$ つの石の座標の組合せを多重集合として数え上げてください。

$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)$ である場合、操作結果の $3$ つの石の座標の組合せとしてありうるのは次の $5$ 通りです：

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

次の図も参考にしてください。