Bạn được cho xâu ~s~ gồm ~n~ kí tự ~\mathtt{g}~, ~\mathtt{e}~, hoặc ~\mathtt{?}~, thoả mãn điều kiện rằng ~s_1 = s_n = \mathtt{g}~. Hãy đếm số mảng ~a~ có độ dài ~n~ thoả mãn các điều kiện sau.

• Mọi phần tử của ~a~ đều là ~1~ hoặc ~-1~.

• Gọi ~p_i = \sum_{j=1}^{i} a_j~ là tổng của ~i~ phần tử đầu tiên của ~a~, với quy ước ~p_0 = 0~. Thế thì:

  • ~p_i \ge 0~ với mọi ~1 \le i \le n~.

  • Với mọi ~1 \le i \le n~ mà ~s_i = \mathtt{g}~, thì ta phải có $$\max(p_0, p_1, \dots, p_i) > \max(p_0, p_1, \dots, p_{i - 1}).$$

  • Với mọi ~1 \le i \le n~ mà ~s_i = \mathtt{e}~, thì ta phải có $$\max(p_0, p_1, \dots, p_i) = \max(p_0, p_1, \dots, p_{i - 1}).$$

Input

Dòng đầu tiên chứa số nguyên ~t~ (~1 \le t \le 1000~) – số lượng test case. Mô tả của mỗi test case như sau.

Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 4000~) — độ dài của ~s~.

Dòng thứ hai chứa xâu ~s~ (~|s| = n, s_i \in \{\mathtt{g}, \mathtt{e}, \mathtt{?}\}, s_1 = s_n = \mathtt{g}~).

Đảm bảo rằng tổng ~n^2~ qua tất cả các test case không quá ~30 \cdot 10^6~.

Output

Với mỗi test case, in ra một số nguyên là số lượng mảng ~a~ thoả mãn các điều kiện trên đề bài. Do số này có thể rất lớn, hãy in ra đáp án dưới 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

Ở test case thứ nhất, mảng duy nhất thoả mãn là ~a = [1, -1, 1, 1]~, với ~p = [1, 0, 1, 2]~:

• Tại ~i = 1~, ta có ~\max(p_0, p_1) = 1 > 0 = \max(p_0)~, thoả mãn ~s_1 = \mathtt{g}~.

• Tại ~i = 2~, ta có ~\max(p_0, p_1, p_2) = 1 = 1 = \max(p_0, p_1)~, thoả mãn ~s_2 = \mathtt{e}~.

• Tại ~i = 4~, ta có ~\max(p_0, p_1, p_2, p_3, p_4) = 2 > 1 = \max(p_0, p_1, p_2, p_3)~, thoả mãn ~s_4 = \mathtt{g}~.

Ở test case thứ hai, hai mảng thoả mãn là:

• ~a = [1, 1, 1, 1]~. Ở đây, ~p = [1, 2, 3, 4]~.

• ~a = [1, -1, 1, 1]~. Ở đây, ~p = [1, 0, 1, 2]~.

Ở test case thứ tư, mảng duy nhất thoả mãn là ~a = [1, -1, 1, -1, 1, 1]~ với ~p = [1, 0, 1, 0, 1, 2]~.