English Problem Statement

素练风霜起，苍鹰画作殊。㧐身思狡兔，侧目似愁胡。

绦镟光堪擿，轩楹势可呼。何当击凡鸟，毛血洒平芜。

你是美军的一名王牌飞行员，正驾驶俯冲式战斗机执行轰炸日军“飞龙号”航空母舰的命令。

作战区域是一个三维空域，空域中的一个位置用 $(x,y,z)$ 表示，其中 $x,y$ 表示你在海面上的投影坐标，$z$ 表示高度。不幸的是，日军的“零式”战斗机正从你的身后包抄过来，你只能在 $y\ge |x|$ 的空域飞行。

一开始你位于 $(0,1,h)$ 处，每过一个时刻你的高度 $h$ 都会下降 $1$。出于一些战术目的，在一个时刻内，你会依次执行以下两种战术动作：

1. 桶翻：横向移动一格（由 $(x,y,z)$ 移动到 $(x^{\prime },y,z-0.5)$，满足 $|x^{\prime }-x|=1$）；
2. 机动：横向或纵向移动一格（由 $(x,y,z)$ 移动到 $(x^{\prime },y^{\prime },z-0.5)$，满足 $|x^{\prime }-x|+|y^{\prime }-y|=1$）。

请注意，这个过程中你也不能离开 $y\ge |x|$ 的空域。

"飞龙号"目前正位于 $(a,b)$ 静止不动，你的目标是在你的高度恰好为 $0$ 时，让你在海面上的投影坐标恰好为 $(a,b)$，以达到轰炸“飞龙号”的目的。

战况紧急，请你立即编写一个程序，计算轰炸计划的方案数，由于这个数字很大，请输出答案对 $998244353$ 取模后的值。

两个轰炸计划不同当且仅当存在一个点 $(x,y,z)$，其中一个方案经过了，而另一个方案没有。保证“飞龙号”位于“零式”战斗机的攻击范围外，即 $b\ge |a|$。

输入格式

本题单个测试点内有多组数据。

第一行仅包含一个整数 $T$，表示数据组数。

对于每组数据仅包含一行：共三个整数 $a,b,h$，表示“飞龙号”的位置坐标和你驾驶的飞机目前的高度。

输出格式

对于每组数据，输出仅一行一个整数，表示答案对 $998244353$ 取模后的结果。

样例一

input

3
2 756543 1
1 2 1
1 2 5

output

0
1
615

explanation

对于第一组数据，$a=2$，$b=756543$，$h=1$，当飞龙号位于 $(2,756543)$ 时，你无论如何都无法从 $1$ 高度机动到飞龙号位置。

对于第二组数据，$a=1$，$b=2$，$h=1$，当飞龙号位于 $(1,2)$ 时，你有恰好一种方法可以攻击飞龙号，即先桶翻至 $(1,1,0.5)$，再机动至 $(1,2,0)$。

样例二～八

见附件下载，其中样例 $2i-1,2i$ 满足第 $i$ 个子任务的限制。

限制与约定

本题采用捆绑测试，各个子任务之间开启所有合理的子任务依赖。

设单个测试点中每组数据的 $h$ 的和为 $\sum h$。对于所有数据，保证 $1\le a,b,h\le {10}^6$，$\sum h\le {10}^6$，$b\ge |a|$。

• Subtask 1（5 points）：保证 $\sum h\le 8$；
• Subtask 2（15 points）：保证 $\sum h\le 500$；
• Subtask 3（30 points）：保证 $\sum h\le 2\times {10}^3$；
• Subtask 4（50 points）：无额外约束。

时间限制： $\mathtt{\text{1s}}$

空间限制： $\mathtt{\text{512MB}}$