Note that the memory limit is unusual.

Let's define the sequence of Fibonacci strings as follows: $f_0$ is 0, $f_1$ is 1, $f_i$ is $f_{i-1} + f_{i-2}$ for $i>1$ ($+$ denotes the concatenation of two strings). So, for example, $f_2$ is 10, $f_3$ is 101, $f_4$ is 10110.

For a given string $s$, let's define $g(s)$ as the number of ways to cut it into several (any number, possibly even just one) strings such that none of these strings are Fibonacci strings. For example, if $s$ is 10110101, $g(s) = 3$ since there are three ways to cut it:

• 101101 $+$ 01;
• 1011 $+$ 0101;
• 1011 $+$ 01 $+$ 01.

You are given a sequence of strings $s_1, s_2, \dots, s_n$. Calculate $g(s_1), g(s_1 + s_2), \dots, g(s_1 + s_2 + \ldots + s_n)$. Since these values can be huge, print them modulo $998244353$.

The first line of the input contains one integer $n$ ($1 \le n \le 3 \cdot 10^3$).

Then, $n$ lines follow. The $i$-th line contains the string $s_i$ ($1 \le |s_i| \le 10^3$), consisting of characters 0 and/or 1.

Print $n$ integers, where the $i$-th integer is $g(s_1 + s_2 + \ldots + s_i) \bmod 998244353$.