Let \(f(B_{1}, B_{2}, B_{3})\) denote the answer to the following lemma.

How many pairs of integers \((Y_{1}, Y_{2})\) satisfy all of the following conditions?

• \(10^{B_{1}}\leq Y_{1}\)
• \(10^{B_{2}}\leq Y_{2}\)
• \(Y_{1} + Y_{2}<10^{B_{3}}\)

We want to find the number of pairs of integers \((X_{1}, X_{2})\) that satisfy all of the following conditions:

• \(10^{A_{1} - 1} \leq X_{1}\)
• \(10^{A_{2}-1} \leq X_{2}\)
• \(X_{1} + X_{2} < 10^{A_{3}}\)
• \(10^{A_{1}} \leq X_{1}\) does not hold.
• \(10^{A_{2}} \leq X_{2}\) does not hold.
• \(X_{1} + X_{2} < 10^{A_{3}-1}\) does not hold.

Using the inclusion-exclusion principle, the answer to this problem can be expressed using \(f\) as follows:

\[\sum_{i=0}^{1}\sum_{j=0}^{1}\sum_{k=0}^{1}f(A_{1} - i, A_{2} - j, A_{3} - k)(-1)^{i+j+k} \]

Therefore, it suffices to implement a function that can quickly compute \(f(B_{1}, B_{2}, B_{3})\). For \(f(B_{1}, B_{2}, B_{3})\), the following holds:

• If \(B_{3} \leq \max(B_{1}, B_{2})\), then \(f(B_{1}, B_{2}, B_{3}) = 0\).
• If \(B_{3} > \max(B_{1}, B_{2})\), then \(f(B_{1}, B_{2}, B_{3}) = \dfrac{(10^{B_{3}}-10^{B_{1}}-10^{B_{2}})(10^{B_{3}}-10^{B_{1}}-10^{B_{2}} + 1)}{2}\).

From the above, \(f(B_{1}, B_{2}, B_{3})\) can be computed in \(O(\log(B_{3}))\) time, so this problem can be solved in \(O(\log(A_{3}))\) time per test case.

C++ implementation example

Python implementation example

MOD = 998244353

def f(b1, b2, b3):
    if max(b1, b2) >= b3:
        return 0
    tmp = pow(10, b3, MOD) - pow(10, b1, MOD) - pow(10, b2, MOD)
    return (tmp + 1) * tmp // 2

T = int(input())
for _ in range(T):
    a1, a2, a3 = map(int,input().split())
    ans = 0
    pm = 1
    for i in range(2):
        for j in range(2):
            for k in range(2):
                ans = (ans + f(a1 - i, a2 - j, a3 - k) * pm) % MOD
                pm *= -1
            pm *= -1
        pm *= -1
    print(ans)