C. Бинарные строки это весело
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бинарная строка$$$^\dagger$$$ $$$b$$$ нечетной длины $$$m$$$ называется хорошей, если $$$b_i$$$ — медиана$$$^\ddagger$$$ строки $$$b[1,i]^\S$$$ для всех нечетных индексов $$$i$$$ ($$$1 \leq i \leq m$$$).

Для бинарной строки $$$a$$$ длины $$$k$$$, бинарная строка $$$b$$$ длины $$$2k-1$$$ называется расширением $$$a$$$, если $$$b_{2i-1}=a_i$$$ для всех $$$i$$$ таких, что $$$1 \leq i \leq k$$$. Например, 1001011 и 1101001 являются расширениями строки 1001. строка $$$x=$$$1011011 не является расширением $$$y=$$$1001, так как $$$x_3 \neq y_2$$$. Обратите внимание, что всего существует $$$2^{k-1}$$$ различных расширений $$$a$$$.

Вам дана бинарная строка $$$s$$$ длины $$$n$$$. Найдите сумму количеств хороших расширений по всем префиксам $$$s$$$. Другими словами, найдите $$$\sum_{i=1}^{n} f(s[1,i])$$$, где $$$f(x)$$$ — число хороших расширений строки $$$x$$$. Так как ответ может быть большим, выведите его по модулю $$$998\,244\,353$$$.

$$$^\dagger$$$ Бинарной строкой называется строка, состоящая только из символов $$$\mathtt{0}$$$ и $$$\mathtt{1}$$$.

$$$^\ddagger$$$ Для бинарной строки $$$a$$$ длины $$$2m-1$$$ медианой $$$a$$$ называется (единственный) символ, который встречается не меньше $$$m$$$ раз в $$$a$$$.

$$$^\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$$$.

Вторая строка каждого набора содержит бинарную строку $$$s$$$ длины $$$n$$$, состоящую только из символов 0 и 1.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите ответ по модулю $$$998\,244\,353$$$.

Пример
Входные данные
6
1
1
1
0
2
11
3
010
9
101101111
37
1011011111011010000011011111111011111
Выходные данные
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.