Problem Statement

For a positive integer $n$, define $R_n$ as "the integer obtained by interpreting a string of $n$ consecutive $1$s as a decimal number". For example, $R_3 = 111$.

You are given a positive integer sequence $A = (A_1, A_2, \dots, A_N)$. For $k = 1, 2, \dots, N$, calculate $\mathrm{LCM}(R_{A_1}, R_{A_2}, \dots, R_{A_k}) \bmod 998244353$. Here, $\mathrm{LCM}$ is the function that calculates the least common multiple.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 2 \times 10^5$
• All input values are integers.

Input

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

N
A_1 A_2 \dots A_N

Output

Output $N$ lines. The $k$-th line should contain $\mathrm{LCM}(R_{A_1}, R_{A_2}, \dots, R_{A_k}) \bmod 998244353$.