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$$$.

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}$$$

Wowee Binary String

Examples