如果 $$$b_i$$$ 是 $$$b[1,i]^\S$$$ 的中位数 $$$b[1,i]^\S$$$ 对于所有奇数索引 $$$i$$$ ($$$1 \leq i \leq m$$$),则奇数长度 $$$m$$$ 的二进制字符串 $$$^\dagger$$$ 是好的。
对于长度为 $$$k$$$ 的二进制字符串 $$$a$$$,长度为 $$$2k-1$$$ 的二进制字符串 $$$b$$$ 是 $$$a$$$ 的扩展,如果 $$$b_{2i-1}=a_i$$$ 对于所有 $$$i$$$ 使得 $$$1 \leq i \leq k$$$。例如,1001011 和 1101001 是字符串 1001 的扩展。字符串 $$$x=$$$1011011 不是字符串 $$$y=$$$1001 的扩展,因为 $$$x_3 \neq y_2$$$。请注意,$$$a$$$ 有 $$$2^{k-1}$$$ 不同的扩展名。
给你一个长度为$$$n$$$的二进制字符串$$$s$$$。求 $$$s$$$ 所有前缀上的良好扩展的数量之和。换句话说,找到 $$$\sum_{i=1}^{n} f(s[1,i])$$$,其中 $$$f(x)$$$ 给出字符串 $$$x$$$ 的良好扩展的数量。由于答案可能相当大,因此您只需对 $$$998\,244\,353$$$ 求模即可。
$$$^\dagger$$$ 二进制字符串是其元素为 $$$\mathtt{0}$$$ 或 $$$\mathtt{1}$$$ 的字符串。
$$$^\ddagger$$$ 对于长度为 $$$2m-1$$$ 的二进制字符串 $$$a$$$,$$$a$$$ 的中位数是在 $$$a$$$ 中至少出现 $$$m$$$ 次的(唯一)元素。
$$$^\S$$$ $$$a[l,r]$$$ 表示长度为 $$$r-l+1$$$ 的字符串,由 $$$a_l,a_{l+1},\ldots,a_r$$$ 按顺序串联而成。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$),其中 $$$n$$$ 是二进制字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含长度为$$$n$$$的二进制字符串$$$s$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印答案模 $$$998\,244\,353$$$。
示例
输入 #1
6 1 1 1 0 2 11 3 010 9 101101111 37 1011011111011010000011011111111011111
输出 #1
1 1 3 3 21 365
注意
在第一个和第二个测试用例中,$$$f(s[1,1])=1$$$。
在第三个测试用例中,答案是$$$f(s[1,1])+f(s[1,2])=1+2=3$$$。
在第四个测试用例中,答案是$$$f(s[1,1])+f(s[1,2])+f(s[1,3])=1+1+1=3$$$。
$$$f(\mathtt{11})=2$$$ 因为有两个好的扩展是可能的:101 和 111。
$$$f(\mathtt{01})=1$$$ 因为只有一个好的扩展是可能的:011。