题目描述

给定三个正整数 $A_{1}$、$A_{2}$、$A_{3}$。请你求满足以下所有条件的正整数三元组 $(X_{1}, X_{2}, X_{3})$ 的个数，并将答案对 $998244353$ 取模。

• $X_{1}$ 是一个十进制下有 $A_{1}$ 位的正整数。
• $X_{2}$ 是一个十进制下有 $A_{2}$ 位的正整数。
• $X_{3}$ 是一个十进制下有 $A_{3}$ 位的正整数。
• $X_{1} + X_{2} = X_{3}$。

每个输入文件包含 $T$ 组测试数据，请你分别求解每组数据。

输入格式

输入以以下格式从标准输入读入。

$T$
$\text{case}_{1}$
$\text{case}_{2}$
$\vdots$
$\text{case}_{T}$

每组数据为一行，包含三个整数：

$A_{1}$ $A_{2}$ $A_{3}$

输出格式

请输出 $T$ 行，第 $i$ 行输出第 $i$ 组数据的答案。

样例 1

输入

4
1 1 1
1 6 7
167 167 167
111 666 777

输出

36
45
731780675
0

说明/提示

数据范围

• $1 \leq T \leq 10^{5}$
• $1 \leq A_{i} \leq 10^{9}$
• 输入均为整数。

样例解释 1

对于第 $1$ 组数据，例如 $(X_{1}, X_{2}, X_{3}) = (1, 6, 7), (2, 1, 3)$ 等都满足条件。而 $(X_{1}, X_{2}, X_{3}) = (6, 7, 13), (3, 4, 5)$ 等则不满足条件。满足条件的三元组共有 $36$ 种，因此输出 $36$。对于第 $3$ 组数据，注意要对 $998244353$ 取模。对于第 $4$ 组数据，也可能不存在满足条件的三元组。

由 ChatGPT 4.1 翻译