Mary loves binary strings.  
Given a binary string S, she defines the *beauty* of the string as the [bitwise XOR] of decimal representations of all substrings of S.

Find the *beauty* of string S. Since the answer can be huge, print it modulo 998244353.

For example, the decimal representation of binary string 1101 is 1\cdot 2^{3} + 1\cdot 2^{2} + 0\cdot 2^{1} + 1\cdot 2^{0} = 8 + 4 + 0+1 = 13. Kindly refer sample explanation for more such examples. 

A string A is a substring of a string B if A can be obtained from B by deleting several (possibly zero) characters from the beginning and several (possibly zero) characters from the end.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of test cases follow.
- First line of each test case contains one integer N - the length of the binary string.
- Second line of each test case contains the binary string S.

------ Output Format ------ 

For each test case, output in a single line, beauty of the string modulo 998244353.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
3
2
10
3
101
4
1111
----- Sample Output 1 ------ 
3
6
12

----- explanation 1 ------ 

Test Case $1$: All substrings of the string $S = 10$ are $[1, 0, 10]$. The decimal representation of these substrings is denoted by the array $[1, 0, 2]$. Bitwise XOR of all these values is $1 \oplus 0 \oplus 2 = 3$.

Test Case $2$: All substrings of the string $S = 101$ are $[1, 0, 1, 10, 01, 101]$. The decimal representation of these substrings is denoted by the array $[1, 0, 1, 2, 1, 5]$. Bitwise XOR of all these values is: $1 \oplus 0 \oplus 1 \oplus 2 \oplus 1 \oplus 5 = 6$.

Test Case $3$: All substrings of the string $S = 1111$ are $[1, 1, 1, 1, 11, 11, 11, 111, 111, 1111]$. The decimal representation of these substrings is denoted by the array $[1, 1, 1, 1, 3, 3, 3, 7, 7, 15]$. Bitwise XOR of all these values is: $1 \oplus 1 \oplus 1 \oplus 1 \oplus 3 \oplus 3 \oplus 3 \oplus 7 \oplus 7 \oplus 15 = 12$.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Probability

Starter code:

Solutions:
mod = 998244353

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())

def solve(lent, binn):
	runningxor = 0
	beauty = 0
	twopow = 1
	for j in range(lent):
		if not j & 1:
			runningxor ^= int(binn[j])
	runningxor %= mod
	for i in range(lent - 1, -1, -1):
		beauty += runningxor * twopow % mod
		beauty %= mod
		if not i & 1:
			runningxor ^= int(binn[i])
		twopow *= 2
		twopow %= mod
	return beauty

def main():
	for i in range(inp()):
		lent = inp()
		string = st()
		print(solve(lent, string))
main()


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	res = list(s)
	curr = 0
	for i in range(0, n, 2):
		curr ^= int(s[i], 2)
		res[i] = str(curr)
		if i + 1 < n:
			res[i + 1] = str(curr)
	print(int(''.join(res), 2) % 998244353)


t = int(input())
for k in range(t):
	n = int(input())
	s = input()
	ans = 0
	mod = 998244353
	prev = 0
	for i in range(n):
		cur = 0
		if i == 0:
			if s[i] == '1':
				cur = 1
			ans = (ans + cur * pow(2, n - 1 - i, mod)) % mod
			prev = cur
			continue
		if s[i] == '1':
			if (i + 1) % 2 != 0:
				if i == n - 1:
					cur = 1 ^ prev
				else:
					cur = 1 ^ prev ^ 0
			else:
				cur = 0 ^ prev
		else:
			cur = prev
		ans = (ans + cur * pow(2, n - 1 - i, mod)) % mod
		prev = cur
	print(ans)


def li():
	return list(map(int, input().split()))

def si():
	return input().split()

def ii():
	return int(input())

def ip():
	return input()
for tastcas in range(int(input())):
	n = ii()
	s = ip()
	a = [0] * n
	c = 1
	if s[0] == '1':
		a[0] = 1
	x = a[0]
	ans = 0
	inf = 998244353
	for j in range(1, n):
		if s[j] == '1':
			x += j + 1
		a[j] = x % 2
	for j in range(n - 1, -1, -1):
		if a[j] == 1:
			ans += c
			ans %= inf
		c *= 2
	print(ans % inf)


t = int(input())
for i in range(t):
	n = int(input())
	b = input()
	a = list([0] * n)
	mod = 998244353
	if b[0] == '1':
		a[0] = 1
	s = a[0]
	for j in range(1, n):
		if b[j] == '1':
			s += j + 1
		a[j] = s
		a[j] %= 2
	p = 1
	ans = 0
	for k in range(n - 1, -1, -1):
		if a[k] == 1:
			ans += p
			ans %= mod
		p *= 2
		p %= mod
	print(ans % mod)


def solve():
	n = int(input())
	bi = input()
	a = list([0] * n)
	MOD = 998244353
	if bi[0] == '1':
		a[0] = 1
	prev = a[0]
	for i in range(1, n):
		if bi[i] == '1':
			prev += i + 1
		a[i] = prev
		a[i] = a[i] % 2
	p = 1
	ans = 0
	for i in range(n - 1, -1, -1):
		if a[i] == 1:
			ans += p
			ans = ans % MOD
		p = p * 2
		p = p % MOD
	print(ans % MOD)
t = int(input())
for i in range(t):
	solve()


T = int(input())
for i in range(T):
	n = int(input())
	s = input()
	m = 998244353
	l = [0] * n
	p = 1
	if s[0] == '1':
		l[0] = 1
	x = l[0]
	for i in range(1, n):
		if s[i] == '1':
			x += i + 1
		l[i] = x
		l[i] = l[i] % 2
	res = 0
	for i in range(n - 1, -1, -1):
		if l[i] == 1:
			res += p
			res %= m
		p *= 2
	p %= m
	print(res % m)


t = int(input())
for i in range(0, t):
	n = int(input())
	s = input()[:n]
	l1 = [0] * n
	p1 = 1
	if s[0] == '1':
		l1[0] = 1
	x = l1[0]
	ans = 0
	for j in range(1, n):
		if s[j] == '1':
			x += j + 1
		l1[j] = x
		l1[j] = l1[j] % 2
	for j in range(n - 1, -1, -1):
		if l1[j] == 1:
			ans += p1
			ans %= 998244353
		p1 *= 2
	p1 %= 998244353
	print(ans % 998244353)


for i in range(int(input())):
	n = int(input())
	s = input()
	a = [0 for i in range(n)]
	if s[0] == '1':
		a[0] = 1
	prev = a[0]
	for i in range(1, n):
		if s[i] == '1':
			prev += i + 1
		a[i] = prev
		a[i] = a[i] % 2
	(p, ans, M) = (1, 0, 998244353)
	for i in range(n - 1, -1, -1):
		if a[i] == 1:
			ans += p
			ans = ans % M
		p = p * 2
		p = p % M
	print(ans % M)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	tmp = list(map(int, list(s)))
	ele = tmp[0]
	sm = 0
	for i in range(0, n):
		sm = sm + tmp[i] * (i + 1)
		tmp[i] = sm % 2
	ans = tmp[0]
	for i in range(1, n):
		ans = (ans * 2 + tmp[i]) % 998244353
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	c = [0] * n
	c[0] = int(a[0])
	for i in range(1, n):
		if i % 2 == 0:
			c[i] = int(a[i]) ^ c[i - 1]
		else:
			c[i] = c[i - 1]
	print(int(''.join(map(str, c)), base=2) % 998244353)


for t in range(int(input())):
	n = int(input())
	s = input()
	ans = ''
	x = 0
	for i in range(n):
		if i % 2 == 0:
			x = x ^ int(s[i])
			ans += str(x)
		else:
			ans += str(x)
	print(int(ans, 2) % 998244353)


import sys
MOD = 998244353
toks = (tok for tok in sys.stdin.read().split())
T = int(next(toks))
for _ in range(T):
	N = int(next(toks))
	S = next(toks)
	ans = 0
	numOn = 0
	for i in range(N):
		if S[i] == '1':
			numOn += i + 1
		if numOn & 1 == 1:
			ans += pow(2, N - i - 1, MOD)
			ans %= MOD
	print(ans)


mod = 998244353
for _ in range(int(input())):
	n = int(input())
	s = input()
	arr = [0] * n
	for i in range(n):
		if s[i] == '1':
			arr[n - i - 1] += i + 1
	for i in range(n - 2, -1, -1):
		arr[i] += arr[i + 1]
	ans = 0
	c = 1
	for i in range(n):
		if arr[i] % 2:
			ans = (ans + c) % mod
		c = c * 2 % mod
	print(ans)


def binaryToDecimal(binary):
	binary1 = binary
	(decimal, i, n) = (0, 0, 0)
	while binary != 0:
		dec = binary % 10
		decimal = decimal + dec * pow(2, i)
		binary = binary // 10
		i += 1
	return decimal
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = 0
	c = 0
	c1 = 0
	j = 1
	p = 1
	l = [0] * n
	for i in range(n):
		if s[i] == '1':
			l[n - i - 1] = i + 1
	for i in range(n - 2, -1, -1):
		l[i] += l[i + 1]
	for i in range(n):
		if l[i] % 2:
			ans += p
		ans = ans % 998244353
		p = p * 2 % 998244353
	print(ans)


for t in range(int(input())):
	n = int(input())
	s = input()
	l = []
	it = 1
	for i in s:
		c = int(i) * it
		if c == 0:
			l.append('0')
		elif c % 2 == 0:
			l.append('0')
		else:
			l.append('1')
		it = it + 1
	for i in range(1, len(l)):
		if l[i] == '1' and l[i - 1] == '1':
			l[i] = '0'
		elif l[i] == '1' and l[i - 1] == '0':
			l[i] = '1'
		elif l[i] == '0' and l[i - 1] == '1':
			l[i] = '1'
		else:
			l[i] = '0'
	ans = ''.join(l)
	print(int(ans, 2) % 998244353)


t = int(input())
for _ in range(t):
	N = int(input())
	S = input()
	mo = 998244353
	x = [0] * N
	y = 1
	if S[0] == '1':
		x[0] = 1
	a = x[0]
	for i in range(1, N):
		if S[i] == '1':
			a = a + i + 1
		x[i] = a
		x[i] = x[i] % 2
	b = 0
	for i in range(N - 1, -1, -1):
		if x[i] == 1:
			b = b + y
			b = b % mo
		y = y * 2
	y = y % mo
	print(b % mo)


for _ in range(int(input())):
	n = int(input())
	s = input()
	res = []
	for i in range(n):
		if i == 0:
			res.append(int(s[i]))
		elif i % 2 == 0:
			res.append(res[-1] ^ int(s[i]))
		else:
			res.append(res[-1])
	mul = 1
	ans = 0
	mod = 998244353
	for ele in res[::-1]:
		ans += mul * ele
		mul *= 2
		mul %= mod
		ans = ans % mod
	print(ans % mod)


m = 998244353
for i in range(int(input())):
	n = int(input())
	s = input()
	a = [0] * n
	for i in range(n):
		if s[i] == '1':
			a[n - i - 1] = i + 1
	for i in range(n - 2, -1, -1):
		a[i] += a[i + 1]
	c = 1
	s = 0
	for i in range(n):
		if a[i] % 2 != 0:
			s = (s + c % m) % m
		c = c % m * 2 % m
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	m = 998244353
	a = n * [0]
	c = 1
	ans = 0
	if s[0] == '1':
		a[0] = 1
	arr = a[0]
	for i in range(1, n):
		if s[i] == '1':
			arr += i + 1
		a[i] = arr
		a[i] = a[i] % 2
	for i in range(n - 1, -1, -1):
		if a[i] == 1:
			ans += c
			ans = ans % m
		c = c * 2
		c = c % m
	print(ans % m)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = ['0'] * n
	c = 0
	if s[0] == '1':
		a[0] = '1'
		c = 1
	for i in range(1, n):
		if s[i] == '1':
			c += i + 1
		a[i] = str(c % 2)
	sharma = ''.join(a)
	ans = int(sharma, 2) % 998244353
	print(ans)


t = int(input())
for i in range(0, t):
	n = int(input())
	s = input()
	ans = 0
	size = len(s)
	pr = curr = 0
	for i in range(0, size):
		if i % 2 == 0:
			curr = (s[i] == '1') != pr
		pr = curr
		if curr:
			ans |= 1 << size - i - 1
	print(ans % 998244353)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	ans = s[0]
	for i in range(1, n):
		if s[i] == '1':
			p = 0
			if i % 2 == 0:
				p = int(ans[-1]) ^ 1
			else:
				p = int(ans[-1]) ^ 0
			ans += str(p)
		else:
			p = 0 ^ int(ans[-1])
			ans += str(p)
	mod = 998244353
	final_ans = int(ans, 2) % mod
	print(final_ans)


import math, bisect, heapq, random, sys, itertools
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
ints = lambda : tuple(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p2 = [1]
p = 10 ** 9 + 7
ANS = []
p = 998244353
for t in range(int(input())):
	n = int(input())
	a = input()
	pref = [0] * n
	for i in range(n):
		if i % 2 == 0 and a[i] == '1':
			pref[i] = 1
	ans = []
	x = 0
	for i in pref:
		x ^= i
		ans.append(x)
	res = 0
	ind = 0
	for i in ans[::-1]:
		if i == 1:
			res = (res + pow(2, ind, p)) % p
		ind += 1
	print(res)


for _ in range(int(input())):
	(sum, ans, n, a) = (0, 0, int(input()), input())
	for i in range(n):
		sum += int(a[i]) * (i + 1)
		ans += (1 << n - i - 1) * (sum % 2)
	print(ans % 998244353)


for _ in range(int(input())):
	n = int(input())
	s = input()
	mod = 998244353
	c1 = 2
	ans = 0
	res = [int(s[0])]
	le = len(s)
	for i in range(1, le):
		if int(s[i]) == 0:
			res.append(res[-1])
		elif c1 % 2 == 0:
			res.append(res[-1])
		elif res[-1] == 0:
			res.append(1)
		else:
			res.append(0)
		c1 += 1
	p = 2
	ans += res[-1]
	for i in range(le - 2, -1, -1):
		if res[i] == 1:
			ans += p
		ans %= mod
		p *= 2
		p %= mod
	print(ans)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		n = inpu()
		s = inp()
		ans = 0
		arr = [0] * n
		b = 0
		for i in range(n):
			if s[i] == '1':
				b += i + 1
			arr[i] = b % 2
		for i in range(n - 1, -1, -1):
			if arr[i] == 1:
				ans += pow(2, n - i - 1, M1)
		print(ans % M1)
main()


M = 998244353
for _ in range(int(input())):
	x = int(input())
	s = str(input())
	arr = [0] * x
	ans = 0
	for i in range(x - 1, -1, -1):
		if s[i] == '1':
			arr[x - i - 1] = i + 1
	for i in range(x - 2, -1, -1):
		arr[i] += arr[i + 1]
	c = 1
	for i in arr:
		if i % 2:
			ans += c
		ans %= M
		c = c * 2 % M
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	lst = [0] * n
	for j in range(n):
		if s[j] == '1':
			lst[n - j - 1] = j + 1
	k = n - 2
	while k >= 0:
		lst[k] += lst[k + 1]
		k -= 1
	ans = 0
	bitpower = 1
	for l in range(n):
		if lst[l] % 2 != 0:
			ans += bitpower
			ans = ans % 998244353
		bitpower = bitpower * 2 % 998244353
	print(ans)


def solve(s, r, g):
	for j in s[2::2]:
		a = int(r)
		b = int(j)
		z = (a + b) % 2
		r = str(z)
		g = g + r + r
	return g

def bintoDec(s, n):
	return int(s[0:n], 2)
t = int(input(''))
while t > 0:
	n = int(input(''))
	s = input('')
	r = s[0]
	g = r + r
	g = solve(s, r, g)
	k = bintoDec(g, n)
	print(k % 998244353)
	t = t - 1


for M in range(int(input())):
	N = int(input())
	ST = input()
	mod = 998244353
	l = [0] * N
	P = 1
	if ST[0] == '1':
		l[0] = 1
	x = l[0]
	for i in range(1, N):
		if ST[i] == '1':
			x += i + 1
		l[i] = x
		l[i] = l[i] % 2
	Rs = 0
	for i in range(N - 1, -1, -1):
		if l[i] == 1:
			Rs += P
			Rs %= mod
		P *= 2
	P %= mod
	print(Rs % mod)


import math
import os
import random
import re
import sys
mod = 998244353
T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	(c, ans) = (1, 0)
	A = [0] * N
	if S[0] == '1':
		A[0] = 1
	B = A[0]
	for i in range(1, N):
		if S[i] == '1':
			B += i + 1
		A[i] = B
		A[i] %= 2
	for i in range(N - 1, -1, -1):
		if A[i] == 1:
			ans += c
			ans %= mod
		c *= 2
		c %= mod
	print(int(ans % mod))


t = int(input())
mod = 998244353
for i in range(t):
	n = int(input())
	li = [0] * n
	st = input()
	s = 1
	if st[0] == '1':
		li[0] = 1
	x = li[0]
	for i in range(1, n):
		if st[i] == '1':
			x += i + 1
		li[i] = x
		li[i] = li[i] % 2
	sumi = 0
	for i in range(n - 1, -1, -1):
		if li[i] == 1:
			sumi += s
			sumi %= mod
		s *= 2
	s %= mod
	print(sumi % mod)


t = int(input())
d = {}
while t:
	n = int(input())
	s = input().strip()
	a = [0] * n
	c = 1
	sol = 0
	if s[0] == '1':
		a[0] = 1
	temp = a[0]
	for i in range(1, n):
		if s[i] == '1':
			temp += i + 1
		a[i] = temp % 2
	for i in range(n - 1, -1, -1):
		if a[i] == 1:
			sol += c
			sol = sol % 998244353
		c = c * 2
		c = c % 998244353
	print(sol % 998244353)
	t -= 1


testcases = int(input())
for _ in range(testcases):
	n = int(input())
	st = input()
	for i in range(100):
		for j in range(101):
			a = 1
	li = [0] * n
	high = 1
	res = 0
	mod = 998244353
	if st[0] == '1':
		li[0] = 1
	pivot = li[0]
	for i in range(1, n):
		if st[i] == '1':
			pivot += i + 1
		li[i] = pivot
		li[i] = li[i] % 2
	for i in range(n - 1, -1, -1):
		if li[i] == 1:
			res += high
			res = res % mod
		high = high * 2
		h = high % mod
	print(res % mod)


for i in range(int(input())):
	n = int(input())
	s = input()
	mod = 998244353
	ans = [0] * n
	k = 1
	if s[0] == '1':
		ans[0] = 1
	x = ans[0]
	for i in range(1, n):
		if s[i] == '1':
			x += i + 1
		ans[i] = x
		ans[i] = ans[i] % 2
	r = 0
	for i in range(n - 1, -1, -1):
		if ans[i] == 1:
			r += k
			r %= mod
		k *= 2
	k %= mod
	print(r % mod)


for _ in range(int(input())):
	n = int(input())
	s = input()
	modulo = 998244353
	l = [0] * n
	p = 1
	if s[0] == '1':
		l[0] = 1
	x = l[0]
	for i in range(1, n):
		if s[i] == '1':
			x += i + 1
		l[i] = x
		l[i] = l[i] % 2
	res = 0
	for i in range(n - 1, -1, -1):
		if l[i] == 1:
			res += p
			res %= modulo
		p *= 2
	p %= modulo
	print(res % modulo)


for i in range(int(input())):
	N = int(input())
	str = input()
	m = 998244353
	len = [0] * N
	p = 1
	if str[0] == '1':
		len[0] = 1
	y = len[0]
	for i in range(1, N):
		if str[i] == '1':
			y += i + 1
		len[i] = y
		len[i] = len[i] % 2
	sol = 0
	for i in range(N - 1, -1, -1):
		if len[i] == 1:
			sol += p
			sol %= m
		p *= 2
	p %= m
	print(sol % m)


for m in range(int(input())):
	n = int(input())
	st = input()
	modu = 998244353
	l = [0] * n
	p = 1
	if st[0] == '1':
		l[0] = 1
	x = l[0]
	for i in range(1, n):
		if st[i] == '1':
			x += i + 1
		l[i] = x
		l[i] = l[i] % 2
	rs = 0
	for i in range(n - 1, -1, -1):
		if l[i] == 1:
			rs += p
			rs %= modu
		p *= 2
	p %= modu
	print(rs % modu)


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = input()
		a = [0] * n
		c = 1
		ans = 0
		mod = 998244353
		if s[0] == '1':
			a[0] = 1
		arr = a[0]
		for i in range(1, n):
			if s[i] == '1':
				arr += i + 1
			a[i] = arr
			a[i] = a[i] % 2
		for i in range(n - 1, -1, -1):
			if a[i] == 1:
				ans += c
				ans = ans % mod
			c = c * 2
			c = c % mod
		print(ans % mod)
except:
	pass


for _ in range(int(input())):
	l = int(input())
	n = input()
	fn = 0
	lx = 0
	for i in range(l):
		if i % 2 == 0:
			lx = lx ^ int(n[i])
		fn = fn * 10 + lx
	dc = 0
	pt = 1
	while fn:
		dc += fn % 10 * pt
		pt *= 2
		fn //= 10
	print(dc % 998244353)


t = int(input())
for _ in range(t):
	n = int(input())
	st = input()
	a = [0] * n
	h = 1
	ans = 0
	if st[0] == '1':
		a[0] = 1
	pv = a[0]
	for i in range(1, n):
		if st[i] == '1':
			pv += i + 1
		a[i] = pv
		a[i] = a[i] % 2
	for i in range(n - 1, -1, -1):
		if a[i] == 1:
			ans += h
			ans = ans % 998244353
		h = h * 2
		h = h % 998244353
	print(ans % 998244353)


def solution(li, n):
	a = 0
	modulo = 998244353
	i = 0
	p = 2 ** (n - 1)
	while i < n:
		if li[i] % 2 != 0:
			a += p
			a = a % modulo
		p //= 2
		i += 1
	return a

def main():
	t = int(input())
	while t > 0:
		n = int(input())
		S = input()
		li = [0] * n
		modulo = 998244353
		i = 1
		s = 0
		p = 0
		ans = 0
		while i <= n:
			if S[i - 1] == '1':
				s += i
			li[i - 1] = s
			i += 1
		ans = solution(li, n)
		print(ans % modulo)
		t -= 1
main()


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	ans = ''
	p = 0
	for i in range(n):
		if i % 2 == 0:
			p = p ^ int(a[i])
			ans += str(p)
		else:
			ans += str(p)
	print(int(ans, 2) % 998244353)


import sys
import re

def main():
	n_case = int(sys.stdin.readline())
	for i_case in range(n_case):
		n = int(sys.stdin.readline())
		s: str = sys.stdin.readline().strip()
		flag: list[int] = [0] * (len(s) + 1)
		for (idx, ch) in enumerate(s):
			if ch == '0':
				continue
			if idx % 2 == 1:
				continue
			(lo, hi) = (0, len(s) - idx - 1)
			flag[lo] += 1
			flag[hi + 1] += 1
		(ret, cur) = ('', 0)
		for v in flag:
			if v % 2 == 1:
				cur = 1 - cur
			ret = str(cur) + ret
		ans = 0
		for x in ret:
			ans = (ans * 2 + int(x)) % 998244353
		print(ans)
main()


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	mod = 998244353
	arr = [0] * n
	p = 1
	if s[0] == '1':
		arr[0] = 1
	x = arr[0]
	for i in range(1, n):
		if s[i] == '1':
			x += i + 1
		arr[i] = x
		arr[i] = arr[i] % 2
	res = 0
	for i in range(n - 1, -1, -1):
		if arr[i] == 1:
			res += p
			res %= mod
		p *= 2
	p %= mod
	print(res % mod)


from sys import stdin, stdout
from collections import Counter as co, defaultdict as dd
import math
mod = int(1000000000.0 + 7)

def fibcompute():
	ans = {1: [[0, 1], [1, 1]]}
	l = [1]
	i = 2
	while i <= 10 ** 18:
		ans[i] = matmul(ans[i / 2], ans[i / 2])
		l.append(i)
		i *= 2
	return [ans, l]

def listi():
	return list(map(int, stdin.readline().strip().split()))

def multii():
	return map(int, stdin.readline().strip().split())

def inti():
	return int(stdin.readline().strip())

def stri():
	return stdin.readline().strip()

def matmul(a, b):
	return [[(a[0][0] % mod * b[0][0] % mod % mod + a[0][1] % mod * b[1][0] % mod % mod) % mod, (a[0][0] % mod * b[0][1] % mod % mod + a[0][1] % mod * b[1][1] % mod % mod) % mod], [(a[1][0] % mod * b[0][0] % mod % mod + a[1][1] % mod * b[1][0] % mod % mod) % mod, (a[1][0] % mod * b[0][1] % mod % mod + a[1][1] % mod * b[1][1] % mod % mod) % mod]]

def isprime(n):
	if n == 1:
		return 0
	c = 0
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			c = 1
			break
	if c == 0:
		return 1
	else:
		return 0

def noofdivisors(n):
	c = 0
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			if n == i ** 2:
				c += 1
			else:
				c += 2
	return c

def fibgreedy(n):
	ans = []
	s = bin(n)[2:]
	ls = len(s)
	for i in range(ls):
		if s[i] != '0':
			ans.append(2 ** (ls - i - 1) * int(s[i]))
	return ans
m = 998244353

def solve():
	n = inti()
	s = stri()
	a = [0] * n
	c = 1
	ans = 0
	if s[0] == '1':
		a[0] = 1
	flag = a[0]
	for i in range(1, n):
		if s[i] == '1':
			flag += i + 1
		a[i] = flag
		a[i] %= 2
	for i in range(n - 1, -1, -1):
		if a[i] == 1:
			ans = (ans % m + c % m) % m
		c = c % m * 2 % m
	print(ans)
t = inti()
for _ in range(t):
	solve()


def function():
	n = int(input())
	s = input()
	sol = ''
	prev = 0
	for i in range(n):
		if s[i] == '1':
			prev = prev + (i + 1)
			if prev % 2 == 0:
				sol = sol + '0'
			else:
				sol = sol + '1'
		elif prev % 2 == 0:
			sol = sol + '0'
		else:
			sol = sol + '1'
	print(int(sol, 2) % 998244353)
for i in range(int(input())):
	function()


T = int(input())
mod = 998244353

def bin_dec(S):
	ans = 0
	for i in range(len(S)):
		ans = ans + int(S[i]) * (2 ** (len(S) - i - 1) % mod)
		ans = ans % mod
	return ans
for i in range(T):
	l = []
	N = int(input())
	S = input()
	ans = 0
	for i in range(0, len(S), 2):
		ans = ans ^ int(S[i])
		l.append(ans)
	new_string = ''
	for j in range(0, len(S)):
		new_string = str(l[(len(S) - 1 - j) // 2]) + new_string
	val = int(new_string, 2)
	print(val % mod)


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = []
	if s[0] == '1':
		l.append(1)
	else:
		l.append(0)
	cnt = l[0]
	for x in range(1, n):
		if s[x] == '1':
			cnt = cnt + x + 1
		l.append(cnt % 2)
	a = ''.join(list(map(str, l)))
	print(int(a, 2) % 998244353)


def ch(st, sle):
	pos = [0] * sle
	mod = 998244353
	r = 1
	if st[0] == '1':
		pos[0] = 1
	y = pos[0]
	for i in range(1, sle):
		if st[i] == '1':
			y += i + 1
		pos[i] = y
		pos[i] %= 2
	ans = 0
	for i in range(sle - 1, -1, -1):
		if pos[i] == 1:
			ans += r
			ans %= mod
		r *= 2
	return ans % mod
x = int(input())
for i in range(x):
	y = int(input())
	s = input()
	print(ch(s, y))


t = int(input())
while t:
	l = int(input())
	s = input()
	a = [0 for i in range(l)]
	c = 1
	sol = 0
	if s[0] == '1':
		a[0] = 1
	arr = a[0]
	for i in range(1, l):
		if s[i] == '1':
			arr += i + 1
		a[i] = arr
		a[i] = a[i] % 2
	for i in range(l - 1, -1, -1):
		if a[i] == 1:
			sol += c
			sol %= 998244353
		c = c * 2
		c = c % 998244353
	print(sol)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	bs = input()
	lis = [0] * n
	temp = 0
	if int(bs[0]):
		temp += 1
	ind = 1
	cop = temp
	lis[0] = temp
	while ind < n:
		if int(bs[ind]):
			cop += ind + 1
		lis[ind] = cop % 2
		ind += 1
	ind = n - 1
	add_var = 1
	res = 0
	while ind >= 0:
		if int(lis[ind]):
			res += add_var % 998244353
		add_var = add_var * 2 % 998244353
		ind -= 1
	print(res % 998244353)


for t in range(int(input())):
	mod = 998244353
	n = int(input())
	s = input()
	a = list([0] * n)
	if s[0] == '1':
		a[0] = 1
	pre = a[0]
	for i in range(1, n):
		if s[i] == '1':
			pre += i + 1
		a[i] = pre
		a[i] = a[i] % 2
	p = 1
	ans = 0
	for i in range(n - 1, -1, -1):
		if a[i] == 1:
			ans += p
			ans = ans % mod
		p = p * 2
		p = p % mod
	print(ans % mod)


mod = 998244353
from sys import stdin, stdout
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	ans = 0
	r = 0
	for i in range(n):
		r += (i + 1) * int(s[i])
		if r % 2 == 1:
			ans += pow(2, n - i - 1, mod)
	print(ans % mod)


for _ in range(int(input())):
	n = int(input())
	a = input()
	x = []
	x.append(a[0])
	for i in range(1, n):
		if a[i] == '0':
			x.append(str(int(x[i - 1]) ^ 0))
		elif a[i] == '1' and (i + 1) % 2 == 1:
			x.append(str(1 ^ int(x[i - 1])))
		else:
			x.append(str(int(x[i - 1]) ^ 0))
	x = str(''.join(x))
	x = int(x, 2)
	print(x % 998244353)


test_cases = int(input())
for i in range(test_cases):
	nmbr = int(input())
	max_val = 998244353
	nmbr2 = input()
	li = []
	first = 1
	second = 0
	for i in range(nmbr):
		li.append(0)
	if nmbr2[0] == '1':
		li[0] = 1
	list2 = []
	list2 = li[0]
	for i in range(1, nmbr):
		if nmbr2[i] == '1':
			list2 += i + 1
		li[i] = list2
		li[i] = li[i] % 2
	for i in range(nmbr - 1, -1, -1):
		if li[i] == 1:
			second += first
			second = second % max_val
		first = first * 2
		first = first % max_val
	print(second % max_val)


for i in range(int(input())):
	n = int(input())
	st = input()
	m = 998244353
	l = [0] * n
	pr = 1
	if st[0] == '1':
		l[0] = 1
	x = l[0]
	for i in range(1, n):
		if st[i] == '1':
			x += i + 1
		l[i] = x
		l[i] = l[i] % 2
	res = 0
	for i in range(n - 1, -1, -1):
		if l[i] == 1:
			res += pr
			res %= m
		pr *= 2
	pr %= m
	print(res % m)


for t in range(int(input())):
	n = int(input())
	s = input()
	a = [0] * n
	c = 1
	k = 0
	if s[0] == '1':
		a[0] = 1
	arr = a[0]
	for i in range(1, n):
		if s[i] == '1':
			arr += i + 1
		a[i] = arr
		a[i] = a[i] % 2
	i = n - 1
	while i > -1:
		if a[i] == 1:
			k += c
			k = k % 998244353
		c = c * 2
		c = c % 998244353
		i -= 1
	print(k % 998244353)


try:
	for _ in range(int(input())):
		n = int(input())
		s = [int(i) for i in input()]
		index = [s[0]]
		ans = s[0]
		for i in range(1, n):
			ans ^= s[i] ^ s[i] if i % 2 == 1 else s[i]
			index.append(ans)
		print(int(''.join(map(str, index)), 2) % 998244353)
except Exception as e:
	raise e


num = int(input())
n = []
a = []
for i in range(0, num):
	n.append(int(input()))
	a.append(input())
for i in range(0, num):
	arr = 0
	sum1 = 0
	product = 2 ** (n[i] - 1)
	for j in range(0, n[i]):
		sum1 += int(a[i][j]) * (j + 1)
		arr += sum1 % 2 * product
		product = product // 2
	print(arr % 998244353)


for _ in range(int(input())):
	a = int(input())
	b = input()
	out = ''
	z = [0 for i in range(a)]
	c = 0
	if b[0] == '1':
		z[0] = 1
		c = z[0]
	for i in range(1, a):
		if b[i] == '1':
			c += i + 1
		z[i] = c % 2
	for i in z:
		out += str(i)
	print(int(out, 2) % 998244353)


m = 998244353
for _ in range(int(input())):
	n = int(input())
	s = input()
	temp = [0] * n
	(i, ans, p) = (0, 0, 1)
	if s[0] == '0':
		temp[0] = 0
	else:
		temp[0] = 1
	t1 = temp[0]
	for i in range(1, n):
		if s[i] == '1':
			t1 += i + 1
		temp[i] = t1 % 2
	j = n - 1
	while j >= 0:
		if temp[j] != 0:
			ans += p
		p *= 2
		(p, ans) = (p % m, ans % m)
		j -= 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	s = input()
	modul = 998244353
	l = [0] * n
	b = 1
	if s[0] == '1':
		l[0] = 1
	x = l[0]
	for i in range(1, n):
		if s[i] == '1':
			x += i + 1
		l[i] = x
		l[i] = l[i] % 2
	rem = 0
	for i in range(n - 1, -1, -1):
		if l[i] == 1:
			rem += b
			rem %= modul
		b *= 2
	b %= modul
	ans = rem % modul
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	nu = [0] * n
	v = 1
	if s[0] == '1':
		nu[0] = 1
	x = nu[0]
	ans = 0
	for i in range(1, n):
		if s[i] == '1':
			x += i + 1
		nu[i] = x
		nu[i] = nu[i] % 2
	for i in range(n - 1, -1, -1):
		if nu[i] == 1:
			ans += v
			ans %= 998244353
		v *= 2
	print(ans % 998244353)