Problem Statement

A non-empty string where every character is A or B is called an AB string.

A set $X$ consisting of AB strings is called a good set when it satisfies the following:

• Every AB string of length $10^{100}$ has some element of $X$ as a prefix.

You are given distinct AB strings $S_1, S_2, \ldots, S_N$. For each $k=1,2,\ldots,N$, find the number, modulo $998244353$, of subsets of the set $\lbrace S_1,S_2,\ldots,S_k\rbrace$ that are good sets.

Constraints

• $1\leq N\leq 2\times 10^5$
• $S_1, S_2, \ldots, S_N$ are distinct AB strings.
• $\sum_{1\leq i\leq N}|S_i|\leq 5\times 10^5$

Input

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

N
S_1
S_2
\vdots
S_N

Output

Output $N$ lines. The $k$-th line should contain the number, modulo $998244353$, of subsets of the set $\lbrace S_1,S_2,\ldots,S_k\rbrace$ that are good sets.