Kevin is exploring problems related to binary strings in Chinatown. When he was at a loss, a stranger approached him and introduced a peculiar operation:

• Suppose the current binary string is $ t $, with a length of $ \vert t \vert $. Choose an integer $ 1 \leq p \leq \vert t \vert $. For all $ 1 \leq i \lt p $, simultaneously perform the operation $ t_i = \max(t_i, t_{i+1}) $, and then delete $ t_p $.

For example, suppose the current binary string is 01001, and you choose $ p = 4 $. Perform $ t_i = \max(t_i, t_{i+1}) $ for $t_1$, $t_2$, and $ t_3 $, transforming the string into 11001, then delete $ t_4 $, resulting in 1101.

Kevin finds this strange operation quite interesting. Thus, he wants to ask you: Given a binary string $ s $, how many distinct non-empty binary strings can you obtain through any number of operations (possibly zero)?

Since the answer may be very large, you only need to output the result modulo $998\,244\,353$.

Input

Each test contains multiple test cases. The first line contains a single integer $t$ ($1\le t \le 10^4$) — the number of test cases.

For each test case, the only line contains a binary string $ s $ ($ 1 \le \lvert s \rvert \le 10^6 $).

It is guaranteed that the sum of $\lvert s \rvert$ over all test cases does not exceed $10^6$.

Output

For each test case, print a single integer in the only line of the output — the number of distinct non-empty binary strings you can obtain, modulo $998\,244\,353$.

Note

In the first test case, all the binary strings you can obtain are: 11001, 1001, 1101, 001, 101, 111, 01, 11, and 1. There are $ 9 $ in total.