You are given a string ~s~ consisting of ~n~ characters ~\mathtt{g}~, ~\mathtt{e}~, or ~\mathtt{?}~, satisfying the condition that ~s_1 = s_n = \mathtt{g}~. Count the number of arrays ~a~ of length ~n~ that satisfy the following conditions.

• Every element of ~a~ is either ~1~ or ~-1~.

• Let ~p_i = \sum_{j=1}^{i} a_j~ be the sum of the first ~i~ elements of ~a~, with the convention ~p_0 = 0~. Then:

  • ~p_i \ge 0~ for all ~1 \le i \le n~.

  • For every ~1 \le i \le n~ where ~s_i = \mathtt{g}~, we must have $$\max(p_0, p_1, \dots, p_i) > \max(p_0, p_1, \dots, p_{i - 1}).$$

  • For every ~1 \le i \le n~ where ~s_i = \mathtt{e}~, we must have $$\max(p_0, p_1, \dots, p_i) = \max(p_0, p_1, \dots, p_{i - 1}).$$

Input

The first line contains an integer ~t~ (~1 \le t \le 1000~) – the number of test cases. The description of each test case is as follows.

The first line contains an integer ~n~ (~1 \le n \le 4000~) — the length of ~s~.

The second line contains the string ~s~ (~|s| = n, s_i \in \{\mathtt{g}, \mathtt{e}, \mathtt{?}\}, s_1 = s_n = \mathtt{g}~).

It is guaranteed that the sum of ~n^2~ across all test cases does not exceed ~30 \cdot 10^6~.

Output

For each test case, print an integer representing the number of arrays ~a~ that satisfy the above conditions. Since this number can be very large, print the answer modulo ~998\,244\,353~.

Scoring

Sample Input 1

7
4
ge?g
4
g??g
4
gegg
6
geeeeg
10
g?eg??eegg
10
g????????g
27
geeeee?e??e????e?e?ee?eg??g

Sample Output 1

1
2
0
1
3
49
460

Notes

In the first test case, the only array that satisfies the condition is ~a = [1, -1, 1, 1]~, with ~p = [1, 0, 1, 2]~:

• At ~i = 1~, we have ~\max(p_0, p_1) = 1 > 0 = \max(p_0)~, satisfying ~s_1 = \mathtt{g}~.

• At ~i = 2~, we have ~\max(p_0, p_1, p_2) = 1 = 1 = \max(p_0, p_1)~, satisfying ~s_2 = \mathtt{e}~.

• At ~i = 4~, we have ~\max(p_0, p_1, p_2, p_3, p_4) = 2 > 1 = \max(p_0, p_1, p_2, p_3)~, satisfying ~s_4 = \mathtt{g}~.

In the second test case, two arrays satisfy the condition:

• ~a = [1, 1, 1, 1]~. Here, ~p = [1, 2, 3, 4]~.

• ~a = [1, -1, 1, 1]~. Here, ~p = [1, 0, 1, 2]~.

In the fourth test case, the only array that satisfies the condition is ~a = [1, -1, 1, -1, 1, 1]~ with ~p = [1, 0, 1, 0, 1, 2]~.