There is a variable $X$ with an initial value of $2$, and a string $S$ of length $N$.$S$ consists only of A and M.

For each character $S_i$ of $S$, the following operation is performed.

• If $S_i$ is A, $2$ is added to $X$. If $S_i$ is M, $X$ is multiplied by $2$.

$i$ is initially $1$, and increases by $1$ for every operation performed. Eventually, the sequence of operations end when $i>N$. Every time an operation is performed, print the largest positive integer $k$ such that $2^k$ is a divisor of $X$.

On the first line, a string $S$ of length $N$ ($\leq 10^6$) is given.

On the $i$-th line $(1 \leq i \leq N)$, print one positive integer: the answer after performing the first $i$ operations.

• $N \leq 10^6$
• $S$ consists only of A and M.