该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

给定三个正整数 $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（\le10^5）$ 组测试数据，请你分别求解每组数据。

Format

Input

第一行一个正整数 $T$ ，表示数据组数。

接下来 $T$ 行，每行一组数据，三个不超过 $10^9$ 的正整数，$A_{1}$ 、 $A_{2}$ 和 $A_{3}$ 。

Output

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

Samples

2
1 1 2
1 1 1

45
36

Limitation

1s, 1024KiB for each test case.