write a go solution for Description:
A binary string^dagger b of odd length m is good if b_i is the median^ddagger of b[1,i]^S for all odd indices i (1<=i<=m).

For a binary string a of length k, a binary string b of length 2k-1 is an extension of a if b_2i-1=a_i for all i such that 1<=i<=k. For example, 1001011 and 1101001 are extensions of the string 1001. String x=1011011 is not an extension of string y=1001 because x_3neqy_2. Note that there are 2^k-1 different extensions of a.

You are given a binary string s of length n. Find the sum of the number of good extensions over all prefixes of s. In other words, find sum_i=1^nf(s[1,i]), where f(x) gives number of good extensions of string x. Since the answer can be quite large, you only need to find it modulo 998,244,353.

^dagger A binary string is a string whose elements are either mathtt0 or mathtt1.

^ddagger For a binary string a of length 2m-1, the median of a is the (unique) element that occurs at least m times in a.

^S a[l,r] denotes the string of length r-l+1 which is formed by the concatenation of a_l,a_l+1,ldots,a_r in that order.

Input Format:
Each test contains multiple test cases. The first line contains the number of test cases t (1<=t<=10^4). The description of the test cases follows.

The first line of each test case contains a single integer n (1<=n<=2*10^5), where n is the length of the binary string s.

The second line of each test case contains the binary string s of length n.

It is guaranteed that the sum of n over all test cases does not exceed 2*10^5.

Output Format:
For each test case, print the answer modulo 998,244,353.

Note:
In the first and second test cases, f(s[1,1])=1.

In the third test case, the answer is f(s[1,1])+f(s[1,2])=1+2=3.

In the fourth test case, the answer is f(s[1,1])+f(s[1,2])+f(s[1,3])=1+1+1=3.

f(mathtt11)=2 because two good extensions are possible: 101 and 111.

f(mathtt01)=1 because only one good extension is possible: 011.. Output only the code with no comments, explanation, or additional text.