题目描述

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

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

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

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

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

输入格式

入力は以下の形式で標準入力から与えられます。

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

各テストケースは以下の形式で与えられます。

$a$ $b$ $c$

输出格式

$T$ 行出力してください。$i$ 行目には、$\text{case}_i$ に対する答えを出力してください。

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

5
2
9
70
182333351
5

提示

制約

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

Sample Explanation 1

$(a,b,c)\ =\ (1,3,5)$ である場合、操作結果の $3$ つの石の座標の組合せとしてありうるのは次の $5$ 通りです： - $(1,3,5)$, $(1,1,3)$, $(-1,1,1)$, $(3,5,5)$, $(5,5,7)$ 次の図も参考にしてください。