B'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 <= q i <= q 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 <= q i <= q 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_3 neq y_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}^{n} f(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 mathtt{0} or mathtt{1} . ^ 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. 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 cdot 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 cdot 10^5 . For each test case, print the answer modulo 998 ,244 ,353 . In the first and second test cases, f(s[1,1])=1 . I'...