Statement : H. Wowee Binary String

H. Wowee Binary String

You find yourself with a string $s$ of length $n$ consisting of only the characters $\texttt{0}$, $\texttt{1}$ and $\texttt{?}$. In other words, $s$ is an incomplete binary string. You will do the following operations in order:

replace all $\texttt{?}$ in $s$ with either $\texttt{0}$ or $\texttt{1}$.
then repeat the following any number of times (possibly none): select a substring of $s$ with an even number of occurrences of the character $\texttt{1}$ and delete it. More formally, select two integers $l$, $r$ where $1 \le l \le r \le |s|$ and $\texttt{1}$ occurs in $s_l,s_{l + 1},\ldots,s_r$ an even number of times, then replace $s$ with $s_1,\ldots,s_{l - 1},s_{r + 1},\ldots,s_{|s|}$

Find how many different binary strings can be obtained after performing the operations. As the number could be humungous, find it modulo $998\,244\,353$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line of each testcase contains an integer $n$ ($1 \le n \le 3000$) — the length of the string.

The second line of each test case contains the incomplete binary string $s$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3000$.

Output

For each testcase, output the number of binary strings that can be obtained, modulo $998\,244\,353$.

Example

Input

7
1
?
5
?????
5
?1001
8
10010001
7
00??10?
7
?1?0?1?
16
0??000?00??1?1?0

Output

Note

Note

In the first two testcases, any binary string of length no longer than $n$ can be made.

In the third testcase, the following strings can be made: $\epsilon, \mathtt{0}, \mathtt{1}, \mathtt{01}, \mathtt{11}, \mathtt{001}, \mathtt{011}, \mathtt{101}, \mathtt{111}, \mathtt{0101}, \mathtt{1001}, \mathtt{1101}, \mathtt{01001}, \mathtt{11001}$, where $\epsilon$ represents the empty string.

An example of how $\texttt{1}$ can be made is as follows:

$\mathtt{\color{red}{?}1001} \rightarrow \mathtt{11001}$
$\mathtt{\color{red}{110}01} \rightarrow \mathtt{01}$
$\mathtt{\color{red}{0}1} \rightarrow \mathtt{1}$