Chef has a binary string S. He can replace any occurrence of - 
- 01 with a
- 10 with b
- 010 with ab
- 101 with ba

While doing these operations, Chef noticed that he can end up with different strings depending upon the order of application of the operations. Given the final string containing only a and b, Chef wants to know the number of possible strings he might have began with.

As the number of initial strings can be large, print the result modulo 998244353. 

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line of input denoting S, the final string obtained after applying the operations.

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

For each test case, output the number of original strings that can result in the final string mod 998244353.

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

$1 ≤ T ≤ 5\cdot 10^{4}$
$1 ≤ |S| ≤ 10^{5}$
- The sum of $|S|$ over all test cases won't exceed $5\cdot 10^{5}$.
$S$ consists of $a$ and $b$ only.

----- Sample Input 1 ------ 
3
ab
aa
abb

----- Sample Output 1 ------ 
2
1
2

----- explanation 1 ------ 
Test case $1$: The binary strings that can result in the string $ab$ are $0110$ and $010$.
- $0110$: Replace the first two characters $01$ with $a$ and last two characters $10$ with $b$. Thus, we get $ab$.
- $010$: Replace the characters $010$ with $ab$.

Test case $2$: The only binary string that can result in the string $aa$ is $0101$. In $0101$, we replace the first two characters with $a$ and last two characters with $a$ as well.

Test case $3$: The binary strings that can result in the string $abb$ are $011010$ and $01010$.
- $011010$: Replace the first two characters $01$ with $a$, next two characters $10$ with $b$, and last two characters $10$ with $b$. Thus, we get $abb$.
- $01010$: Replace the characters $010$ with $ab$ and the characters $10$ with $b$.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
mod = 998244353
for _ in range(int(input())):
	s = input()
	n = len(s)
	dp = [1] * (n + 1)
	for i in range(1, n):
		dp[i + 1] = dp[i]
		if s[i] != s[i - 1]:
			dp[i + 1] += dp[i - 1]
		dp[i + 1] %= mod
	print(dp[n])


mod = 998244353
for _ in range(int(input())):
	bstr = [a for a in input()]
	n = len(bstr)
	ali = [0] * (n + 1)
	ali[0] = 1
	ali[1] = 1
	for i in range(1, n):
		if bstr[i] != bstr[i - 1]:
			ali[i + 1] = (ali[i] + ali[i - 1]) % mod
		else:
			ali[i + 1] = ali[i]
	print(ali[n] % mod)


for f in range(int(input())):
	shiv = input().strip()
	N = len(shiv)
	L = [0] * (N + 1)
	L[N] = 1
	L[N - 1] = 1
	for bhav in range(N - 2, -1, -1):
		if shiv[bhav] != shiv[bhav + 1]:
			L[bhav] = (L[bhav + 1] + L[bhav + 2]) % 998244353
		else:
			L[bhav] = L[bhav + 1]
	print(L[0] % 998244353)


for _ in range(int(input())):
	s = input()
	n = len(s)
	x = 1
	y = 1
	z = 1
	val = [1] * (n + 2)
	for i in range(1, n):
		if s[i] == 'a' and s[i - 1] == 'a':
			val[i + 1] = val[i]
		if s[i] == 'a' and s[i - 1] == 'b':
			val[i + 1] = val[i] + val[i - 1]
		if s[i] == 'b' and s[i - 1] == 'b':
			val[i + 1] = val[i]
		if s[i] == 'b' and s[i - 1] == 'a':
			val[i + 1] = val[i] + val[i - 1]
	print(val[n] % 998244353)


for t in range(int(input())):
	s = input()
	arr = [1] + [0] * len(s)
	for i in range(len(s)):
		arr[i + 1] = (arr[i + 1] + arr[i]) % 998244353
		if i != len(s) - 1 and s[i:i + 2] in ['ab', 'ba']:
			arr[i + 2] = (arr[i + 2] + arr[i]) % 998244353
	print(arr[-1])


S = {'a', 'b', 'ab', 'ba'}
for _ in range(int(input())):
	s = input()
	N = len(s)
	dp = [0] * N
	dp[0] = 1
	for i in range(1, N):
		c1 = dp[i - 1]
		c2 = 0
		if s[i - 1:i + 1] in S:
			if i - 2 < 0:
				c2 = 1
			else:
				c2 = dp[i - 2]
		dp[i] = (c1 + c2) % 998244353
	print(dp[-1] % 998244353)


T = int(input())
for _ in range(T):
	S = input()
	N = len(S)
	if N == 1:
		print(1)
	else:
		L = [0] * N
		L[0] = 1
		if S[0] != S[1]:
			L[1] = 2
		else:
			L[1] = 1
		for i in range(2, N):
			if S[i] == S[i - 1]:
				L[i] = L[i - 1]
			else:
				L[i] = L[i - 1] + L[i - 2]
		print(L[N - 1] % 998244353)


mod = 998244353
for _ in range(int(input())):
	s = input()
	if len(s) == 1:
		print(1)
		continue
	l = [0] * len(s)
	l[0] = 1
	if s[0] == s[1]:
		l[1] = 1
	else:
		l[1] = 2
	for i in range(2, len(s)):
		if s[i] != s[i - 1]:
			l[i] = (l[i - 1] + l[i - 2]) % mod
		else:
			l[i] = l[i - 1] % mod
	print(l[-1])


for _ in range(int(input())):
	str1 = input()
	len1 = len(str1)
	if len1 == 1:
		print('1')
		continue
	elif len1 == 2:
		if str1[0] == str1[-1]:
			print('1')
			continue
		else:
			print('2')
			continue
	dp = [0 for i in range(len1)]
	dp[-1] = 1
	if str1[-1] == str1[-2]:
		dp[-2] = 1
	else:
		dp[-2] = 2
	for i in range(-3, -len1 - 1, -1):
		if str1[i] == str1[i + 1]:
			dp[i] = dp[i + 1]
			continue
		else:
			dp[i] = (dp[i + 1] + dp[i + 2]) % 998244353
	print(dp[0])


def bin_sub(s):
	n = len(s)
	mod = 998244353
	prev = 1
	cur = 1
	for i in range(n - 2, -1, -1):
		take = 0
		if s[i] != s[i + 1]:
			take = prev
		ans = (cur + take) % mod
		prev = cur
		cur = ans
	print(cur)
T = int(input())
for _ in range(T):
	s = list(input())
	bin_sub(s)


def bin_sub(s):
	n = len(s)
	mod = 998244353
	group = [0 for _ in range(n + 1)]
	group[n] = 1
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			group[i] = 1
		else:
			take = 0
			if s[i] != s[i + 1]:
				take = group[i + 2]
			group[i] = (group[i + 1] + take) % mod
	print(group[0])
T = int(input())
for _ in range(T):
	s = list(input())
	bin_sub(s)


N = 100010
M = 998244353
f = [1] * N
f[1] = 2
f[2] = 3
for i in range(3, N):
	f[i] = (f[i - 1] + f[i - 2]) % M
t = int(input())
for _ in range(t):
	s = input()
	s += s[-1]
	ans = 1
	x = 0
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			x += 1
		else:
			ans = ans * f[x] % M
			x = 0
	print(ans)


n = int(input())
for k in range(n):
	l = input()
	q = len(l)
	p2 = 1
	p1 = 1
	c = 1
	temp1 = 0
	temp2 = 0
	t = False
	for i in range(1, q):
		temp1 = c
		temp2 = p1
		if l[i] != l[i - 1]:
			if t:
				c = p2 + p1 * 2
			if not t:
				c = p1 * 2
				t = True
			p1 = temp1
			p2 = temp2
		elif l[i] == l[i - 1]:
			if t:
				t = False
				p1 = c
			else:
				t = False
	print(c % 998244353)


for i in range(int(input())):
	s = input()
	c = 1
	p = 1
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			p = c
		else:
			(c, p) = (c + p, c)
	print(c % 998244353)


def solve(s):
	p = 1
	c = 1
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			p = c
		else:
			(c, p) = (c + p, c)
	print(c % 998244353)
for _ in range(int(input())):
	s = input()
	solve(s)


def solve(s):
	p_way = 1
	c_way = 1
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			p_way = c_way
		else:
			(c_way, p_way) = (c_way + p_way, c_way)
	print(c_way % 998244353)
for _ in range(int(input())):
	s = input()
	solve(s)


mod = 998244353
for _ in range(int(input())):
	s = input()
	r = len(s)
	d = [0] * (r + 1)
	d[0] = 1
	d[1] = 1
	for i in range(1, r):
		if s[i] == s[i - 1]:
			d[i + 1] = d[i]
		else:
			d[i + 1] = d[i] + d[i - 1]
	print(d[r] % mod)


mod = 998244353
for t in range(int(input())):
	s = input()
	n = len(s)
	dp = [1] * (n + 1)
	for i in range(2, n + 1):
		if s[i - 1] != s[i - 2]:
			dp[i] = dp[i - 1] + dp[i - 2]
		else:
			dp[i] = dp[i - 1]
	print(dp[n] % mod)


caseCount = int(input())
for _ in range(caseCount):
	s = input()
	length = len(s)
	dp = [0] * (length + 1)
	dp[0] = 1
	dp[1] = 1
	for i in range(1, length):
		if s[i] == s[i - 1]:
			dp[i + 1] = dp[i] % 998244353
		else:
			dp[i + 1] = (dp[i] + dp[i - 1]) % 998244353
	print(dp[length])


mod = 998244353
t = int(input())
for _ in range(t):
	s = input()
	a = [0] * (len(s) + 1)
	(a[-1], a[-2]) = (1, 1)
	for i in range(len(s) - 2, -1, -1):
		if s[i] == s[i + 1]:
			a[i] = a[i + 1]
		else:
			a[i] = (a[i + 1] + a[i + 2]) % mod
	print(a[0] % mod)


def funct(st1):
	dpi = [0] * (len(st1) + 1)
	dpi[-1] = 1
	dpi[-2] = 1
	for k in range(len(st1) - 2, -1, -1):
		if st1[k] == st1[k + 1]:
			dpi[k] = dpi[k + 1]
		else:
			dpi[k] = (dpi[k + 1] + dpi[k + 2]) % 998244353
	return dpi[0] % 998244353

def ma():
	a = int(input())
	while a:
		str = input()
		print(funct(str))
		a -= 1
ma()


from collections import *
from math import *
from sys import *
mod = 998244353
T = int(input())
for _ in range(T):
	B = input()
	A = [0] * (len(B) + 1)
	(A[-1], A[-2]) = (1, 1)
	for i in range(len(B) - 2, -1, -1):
		if B[i] == B[i + 1]:
			A[i] = A[i + 1]
		else:
			A[i] = (A[i + 1] + A[i + 2]) % mod
	print(A[0] % mod)


n = int(input())
for op in range(n):
	st = input()
	li = [0] * (len(st) + 1)
	(li[-1], li[-2]) = (1, 1)
	for k in range(len(st) - 2, -1, -1):
		if st[k] == st[k + 1]:
			li[k] = li[k + 1]
		else:
			li[k] = (li[k + 1] + li[k + 2]) % 998244353
	print(li[0] % 998244353)


def func(base_str):
	if len(base_str) <= 1:
		return 1
	if base_str[0] == base_str[1]:
		return func(base_str[1:])
	else:
		return func(base_str[1:]) + func(base_str[2:])
for _ in range(int(input().strip())):
	x = input().strip()
	n = len(x)
	d = [-1] * (n + 1)
	d[0] = d[1] = 1
	for i in range(2, n + 1):
		d[i] = d[i - 1]
		if x[i - 1] != x[i - 2]:
			d[i] = (d[i] + d[i - 2]) % 998244353
	print(d[n])


for T in range(int(input())):
	s = input()
	n = len(s)
	ans = [1] * (n + 1)
	for i in range(1, n):
		ans[i + 1] = ans[i]
		if s[i] != s[i - 1]:
			ans[i + 1] += ans[i - 1]
	ans[n] = ans[n] % 998244353
	print(ans[n])


for i in range(int(input())):
	S = input()
	L = len(S)
	X = [1] * (L + 1)
	for i in range(1, L):
		X[i + 1] = X[i]
		if S[i] != S[i - 1]:
			X[i + 1] += X[i - 1]
	X[L] %= 998244353
	print(X[L])


def binarySubstring(index):
	ans = b_s_dict[index + 1]
	if s[index] != s[index + 1]:
		if index + 2 < n:
			ans = ans + b_s_dict[index + 2]
		if index + 2 == n:
			ans += 1
	b_s_dict[index] = ans
for _ in range(int(input())):
	s = input()
	n = len(s)
	final_ans = 0
	b_s_dict = {n - 1: 1}
	for i in range(n - 2, -1, -1):
		binarySubstring(i)
	print(b_s_dict[0] % 998244353)


for _ in range(int(input())):
	s = input()
	N = len(s)
	arr = [1] * (N + 1)
	for i in range(1, N):
		arr[i + 1] = arr[i]
		if s[i] != s[i - 1]:
			arr[i + 1] += arr[i - 1]
		arr[i + 1] %= 998244353
	print(arr[N])


testcases = int(input())
for i in range(testcases):
	string = input()
	n = len(string)
	greed = [0] * (n + 1)
	greed[n] = greed[n - 1] = 1
	for j in range(n - 2, -1, -1):
		if string[j] == string[j + 1]:
			greed[j] = greed[j + 1]
		else:
			greed[j] = (greed[j + 1] + greed[j + 2]) % 998244353
	print(greed[0] % 998244353)


def solve():
	s = input()
	n = len(s)
	if n == 1:
		print(1)
		return
	ans = [0] * n
	ans[0] = 1
	ans[1] = 1 + (s[0] != s[1])
	for i in range(2, n):
		ans[i] = ans[i - 1]
		if s[i] != s[i - 1]:
			ans[i] = ans[i - 1] + ans[i - 2] % 998244353
	print(ans[n - 1] % 998244353)
t = int(input())
while t != 0:
	solve()
	t -= 1


def fib(s):
	if len(s) == 1 or len(s) == 0:
		return 1
	if s[0:2] == 'ab' or s[0:2] == 'ba':
		return fib(s[1:]) + fib(s[2:])
	else:
		return fib(s[1:])
t = int(input())
for tr in range(t):
	s = input()
	ab = s.count('ab')
	ba = s.count('ba')
	abb = s.count('abb')
	baa = s.count('baa')
	aab = s.count('aab')
	bba = s.count('bba')
	a = 1
	b = 1
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			(a, b) = (b % 998244353, (a + b) % 998244353)
		else:
			a = b
	print(b % 998244353)


for i in range(int(input())):
	inpStr = input()
	a = 0
	b = 1
	beforeValue = None
	for i in range(len(inpStr) - 1, -1, -1):
		if inpStr[i] != beforeValue:
			b += a
			a = b - a
		else:
			a = b
		beforeValue = inpStr[i]
	print(b % 998244353)


t = int(input())
for i in range(t):
	s = input()
	x = 'c'
	y = 1
	(a, b) = (0, 1)
	for j in range(len(s) - 1, -1, -1):
		if s[j] != x:
			b += a
			a = b - a
		else:
			a = b
		x = s[j]
	print(b % 998244353)


T = int(input())
for i in range(T):
	strr = input()
	x = 'c'
	y = 1
	(a, b) = (0, 1)
	for j in range(len(strr) - 1, -1, -1):
		if strr[j] != x:
			b += a
			a = b - a
		else:
			a = b
		x = strr[j]
	print(b % 998244353)


for i in range(int(input())):
	s = input()
	n = len(s)
	ans = [0] * n
	ans[0] = 1
	if n == 1:
		print(1)
	else:
		ans[1] = 1 + (s[0] != s[1])
		for i in range(2, n):
			ans[i] = ans[i - 1]
			if s[i] != s[i - 1]:
				ans[i] = (ans[i] + ans[i - 2]) % 998244353
		print(ans[n - 1])


for i in range(int(input())):
	a = input()
	m = [1, 1]
	for i in range(1, len(a)):
		if a[i] != a[i - 1]:
			m.append(m[-1] + m[-2])
		else:
			m.append(m[-1])
	print(m[-1] % 998244353)


t = int(input())
for _ in range(0, t):
	s = list(input())
	n = len(s)
	x = 1
	y = 1
	for i in range(0, n - 1):
		if s[i] != s[i + 1]:
			temp = x
			x = x + y
			y = temp
		else:
			y = x
	print(x % 998244353)


for x in range(int(input())):
	a = list(input())
	if len(a) < 2:
		print(1)
		continue
	if len(a) == 2:
		if a == ['a', 'a'] or a == ['b', 'b']:
			print(1)
		else:
			print(2)
		continue
	ans = [1]
	ans.append(2 if a[0] != a[1] else 1)
	for i in range(2, len(a)):
		temp = 0
		if a[i] != a[i - 1]:
			temp = ans[i - 2]
		ans.append(temp + ans[i - 1])
	print(ans[-1] % 998244353)


modd = 998244353
t = int(input())
while t > 0:
	s = str(input())
	n = len(s)
	if n == 1:
		print(1)
	else:
		ans = [0] * n
		ans[0] = 1
		ans[1] = 1 + (s[0] != s[1])
		for i in range(2, n):
			ans[i] = ans[i - 1]
			if s[i - 1] != s[i]:
				ans[i] = (ans[i] + ans[i - 2]) % modd
		print(ans[n - 1])
	t = t - 1


for i in range(int(input())):
	s = input()
	a = [None] * (len(s) + 1)
	a[len(s)] = 1
	a[len(s) - 1] = 1
	for i in reversed(range(len(s) - 1)):
		if s[i] == s[i + 1]:
			a[i] = a[i + 1]
		else:
			a[i] = (a[i + 1] + a[i + 2]) % 998244353
	print(a[0])


mod = 998244353

def solve(s):
	dp = [0 for i in range(len(s))]
	dp[0] = 1
	if len(s) > 1:
		dp[1] = dp[0] + (1 if s[0] != s[1] else 0)
	for i in range(2, len(s)):
		if s[i] == s[i - 1]:
			dp[i] = dp[i - 1]
		else:
			dp[i] = (dp[i - 1] + dp[i - 2]) % mod
	return dp[-1]
for _ in range(int(input())):
	s = input()
	ans = solve(s)
	print(ans % mod)


def soln(s):
	res = 0
	n = len(s)
	mod = 998244353
	dp = [0] * (n + 1)
	dp[-1] = dp[-2] = 1
	for i in range(n - 2, -1, -1):
		if s[i] != s[i + 1]:
			dp[i] = (dp[i + 1] + dp[i + 2]) % mod
		else:
			dp[i] = dp[i + 1]
	return dp[0] % mod
for _ in range(int(input())):
	s = input()
	print(soln(s))


for _ in range(int(input())):
	s = input()
	n = len(s)
	if n == 1:
		print(1)
	else:
		l = []
		l.append(1)
		if s[0] == s[1]:
			l.append(1)
		else:
			l.append(2)
		for i in range(2, n):
			if s[i] == s[i - 1]:
				l.append(l[i - 1])
			else:
				l.append(l[i - 1] + l[i - 2])
		print(l[n - 1] % 998244353)


MOD = 998244353
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	dp = [0] * n
	dp[0] = 1
	for i in range(1, n):
		dp[i] = dp[i - 1]
		if s[i - 1:i + 1] == 'ab' or s[i - 1:i + 1] == 'ba':
			if i >= 2:
				dp[i] = (dp[i] + dp[i - 2]) % MOD
			else:
				dp[i] = (dp[i] + 1) % MOD
	print(dp[n - 1])


def bin_sub(s, n, mod):
	dp = [1 for i in range(n + 1)]
	for i in range(1, n):
		dp[i + 1] = dp[i]
		if s[i] != s[i - 1]:
			dp[i + 1] += dp[i - 1]
		dp[i + 1] %= mod
	return dp[n]
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	mod = 998244353
	print(bin_sub(s, n, mod))


mod = 998244353
for _ in range(int(input())):
	S = input()
	N = len(S)
	DP = [1] * (N + 1)
	for i in range(1, N):
		DP[i + 1] = DP[i]
		if S[i] != S[i - 1]:
			DP[i + 1] += DP[i - 1]
		DP[i + 1] %= mod
	print(DP[N])