Problem Statement

A positive integer $n$ is called a good number if $n$ satisfies the following condition.

• When $n$ is interpreted as a decimal number, let $n_i$ be the value of its $10^i$ place. There exists a non-negative integer $i$ such that $n_{i+2} > n_{i+1} + n_i$.

For a positive integer $n$, define $f(n)$ as the minimum good number greater than or equal to $n$.

You are given a positive integer $N$. Find the value of $f(1) + f(2) + \cdots + f(N)$ modulo $998244353$.

$T$ test cases are given; answer each of them.

Constraints

• All input values are integers.
• $1 \leq T \leq 200$
• $1 \leq N \leq 10^{18}$

Input

The input is given from standard input in the following format.

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format.

$N$

Output

Output the answers to the test cases in order, separated by newlines.

Sample

4
10
668
169231
1000000000000000000

1000
245820
346334860
992299114