B - 1 + 6 = 7 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600

問題文

正の整数 A_{1}, A_{2}, A_{3} が与えられます。 以下の条件を全て満たす正の整数の組 (X_{1}, X_{2}, X_{3}) の場合の数を 998244353 で割ったあまりを求めてください。

  • X_{1}10 進法で A_{1} 桁の正の整数
  • X_{2}10 進法で A_{2} 桁の正の整数
  • X_{3}10 進法で A_{3} 桁の正の整数
  • X_{1} + X_{2} = X_{3}

1 つの入力ファイルにつき T 個のテストケースが与えられるので、それぞれについて解いてください。

制約

  • 1\leq T\leq 10^{5}
  • 1\leq A_{i}\leq 10^{9}
  • 入力は全て整数

入力

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

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

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

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

出力

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


入力例 1

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

出力例 1

36
45
731780675
0

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) などは条件を満たしません。

条件を満たす (X_{1}, X_{2}, X_{3}) の組は 36 通りあるので 36 を出力してください。

3 つ目のケースについて、答えを 998244353 で割ったあまりを出力することに注意してください。

4 つ目のケースについて、条件を満たす (X_{1}, X_{2}, X_{3}) の組が存在しないこともあります。

Score : 600 points

Problem Statement

You are given positive integers A_{1}, A_{2}, A_{3}. Find the number, modulo 998244353, of tuples of positive integers (X_{1}, X_{2}, X_{3}) that satisfy all of the following conditions.

  • X_{1} is a positive integer with A_{1} digits in decimal notation.
  • X_{2} is a positive integer with A_{2} digits in decimal notation.
  • X_{3} is a positive integer with A_{3} digits in decimal notation.
  • X_{1} + X_{2} = X_{3}.

You are given T test cases per input file; solve each of them.

Constraints

  • 1 \leq T \leq 10^{5}
  • 1 \leq A_{i} \leq 10^{9}
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Each case is given in the following format:

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

Output

Print T lines. The i-th line should contain the answer for \text{case}_{i}.


Sample Input 1

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

Sample Output 1

36
45
731780675
0

For the first case, tuples such as (X_{1}, X_{2}, X_{3}) = (1, 6, 7), (2, 1, 3) satisfy the conditions.

On the other hand, tuples such as (X_{1}, X_{2}, X_{3}) = (6, 7, 13), (3, 4, 5) do not.

There are 36 tuples (X_{1}, X_{2}, X_{3}) that satisfy the conditions, so print 36.

For the third case, remember to print the result modulo 998244353.

For the fourth case, there may be no tuples (X_{1}, X_{2}, X_{3}) that satisfy the conditions.