Chef has an array A of length N. 

He can modify this array by applying a special operation any number of times. In one operation, he can:
Select two indices i and j (1≤ i < j ≤ |A|).
Append A_{i} \oplus A_{j} to the end of the array, where \oplus denotes the [bitwise XOR operation]
Remove A_{i} and A_{j} from the array.

Chef wants to maximize the product of all the elements of the array after applying these operations.

Help Chef determine the maximum product he can achieve by applying this operation any (possibly zero) number of times. As this number can be large, print it 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 two lines of input.
- The first line of each test case contains one integer N — the number of elements in the array.
- The second line consists of N space-separated integers A_{1}, A_{2}, \ldots, A_{N} denoting the elements of the array initially.

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

For each test case, output the maximum product he can achieve modulo 998244353.

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

$1 ≤ T ≤ 5\cdot 10^{4}$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $3\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
4
1 2 1 2
2
3 3
2
2 1

----- Sample Output 1 ------ 
9
9
3

----- explanation 1 ------ 
Test case $1$: Chef can make the following operations:
- Operation $1$: Choose $i = 1$ and $j = 2$, append $A_{1}\oplus A_{2} = 1\oplus 2 = 3$ to the end of the array and remove elements $A_{1}$ and $A_{2}$. Thus, the array becomes $[1, 2, 3]$.
- Operation $2$: Choose $i = 1$ and $j = 2$, append $A_{1}\oplus A_{2} = 1\oplus 2 = 3$ to the end of the array and remove elements $A_{1}$ and $A_{2}$. Thus, the array becomes $[3, 3]$.

The product of all elements of the array is $3\times 3 = 9$. It can be shown that this is the maximum product that can be obtained by applying any number of operations on the array.

Test case $2$: The product of all elements of the array is $3\times 3 = 9$. It can be shown that this is the maximum product that can be obtained by applying any number of operations on the array.  
Thus, Chef does not need to perform any operations.

Test case $3$: Chef can make the following operation:
- Operation $1$: Choose $i = 1$ and $j = 2$, append $A_{1}\oplus A_{2} = 1\oplus 2 = 3$ to the end of the array and remove elements $A_{1}$ and $A_{2}$. Thus, the array becomes $[3]$.

The product of all elements is $3$. It can be shown that this is the maximum product that can be obtained by applying any number of operations on the array.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting

Greedy algorithms


Solutions:
MOD = 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	li = sorted(li)
	c = li.count(1)
	for i in range(n):
		if li[i] % 2 == 0 and c > 0:
			li[i] += 1
			c -= 1
	ans = 1
	for i in li:
		ans = ans * i % MOD
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split(' ')))
	odds = sorted([x for x in arr if x % 2 == 1])
	evens = sorted([x for x in arr if x % 2 == 0])
	p = q = 0
	while p < len(odds) and q < len(evens):
		if odds[p] != 1:
			break
		evens[q] += 1
		p += 1
		q += 1
	ans = 1
	for idx in range(p, len(odds)):
		ans = ans * odds[idx] % 998244353
	for ev in evens:
		ans = ans * ev % 998244353
	print(ans)


Test = int(input())
mod = 998244353
for t in range(Test):
	n = int(input())
	lis = map(int, input().split())
	lis = sorted(lis)
	countof1 = lis.count(1)
	for i in range(n):
		if lis[i] % 2 == 0 and countof1 > 0:
			lis[i] += 1
			countof1 -= 1
	ans = 1
	for a in lis:
		ans = ans * a % mod
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	finprod = 1
	aones = a.count(1)
	evs = []
	for e in range(aones, n):
		if a[e] % 2 == 1:
			finprod = finprod * a[e] % 998244353
		else:
			evs.append(a[e])
	evs.sort()
	i = min(aones, len(evs))
	for j in range(len(evs)):
		if j < i:
			finprod = finprod * (evs[j] + 1) % 998244353
		else:
			finprod = finprod * evs[j] % 998244353
	print(finprod % 998244353)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = 998244353
	(o, e) = (1, [])
	for i in a:
		if i & 1:
			o = o * i % m
		else:
			e.append(i)
	c = a.count(1)
	e.sort()
	for i in range(min(c, len(e))):
		e[i] += 1
	for i in e:
		o = o * i % m
	print(o)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	o = []
	e = []
	c = 0
	for i in l:
		if i == 1:
			c += 1
	l.sort()
	p = 1
	for i in l:
		if i % 2 == 0 and c:
			p = p * (i ^ 1) % 998244353
			c -= 1
		else:
			p = p * i % 998244353
	print(p)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 1
	mod = 998244353
	ones = 0
	a.sort()
	for i in range(n):
		if a[i] == 1:
			ones += 1
		elif a[i] % 2 == 0 and ones > 0:
			ones -= 1
			a[i] += 1
		ans = ans * a[i] % mod
	print(ans)


prime = 998244353
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	odds = sorted([x for x in a if x % 2 != 0])
	evens = sorted([x for x in a if x % 2 == 0])
	j = k = 0
	while j < len(odds) and k < len(evens):
		if odds[j] != 1:
			break
		evens[k] += 1
		j += 1
		k += 1
	prod = 1
	for k in range(j, len(odds)):
		prod = prod * odds[k] % prime
	for x in evens:
		prod = prod * x % prime
	print(prod)


mod = 998244353
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	evens = sorted([x for x in a if x % 2 == 0])
	odds = sorted([x for x in a if x % 2 == 1])
	j = k = 0
	while j < len(odds) and k < len(evens):
		if odds[j] != 1:
			break
		evens[k] += 1
		j += 1
		k += 1
	ans = 1
	for i in range(j, len(odds)):
		ans = ans * odds[i] % mod
	for x in evens:
		ans = ans * x % mod
	print(ans)


mod = 998244353
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(evens, odds) = (sorted([x for x in a if x % 2 == 0]), sorted([x for x in a if x % 2 == 1]))
	p = q = 0
	while p < len(odds) and q < len(evens):
		if odds[p] != 1:
			break
		evens[q] += 1
		p += 1
		q += 1
	ans = 1
	for i in range(p, len(odds)):
		ans = ans * odds[i] % mod
	for x in evens:
		ans = ans * x % mod
	print(ans)


MOD = 998244353
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	(odd, even) = ([], [])
	for i in A:
		if i % 2 == 1:
			odd.append(i)
		else:
			even.append(i)
	odd.sort()
	even.sort()
	(i, j) = (0, 0)
	while i < len(odd) and j < len(even):
		if odd[i] > 1:
			break
		even[j] += 1
		i += 1
		j += 1
	product = 1
	for i in odd:
		product = product * i % MOD
	for i in even:
		product = product * i % MOD
	print(product)


mod = 998244353
for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	L.sort()
	c = 0
	while L and L[0] == 1:
		c += 1
		L.pop(0)
	res = 1
	for i in L:
		if i & 1 == 0 and c > 0:
			c -= 1
			i ^= 1
		res *= i
		res %= mod
	print(res)


mod = 998244353
for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	L.sort()
	prod = 1
	c = L.count(1)
	for i in range(n):
		if L[i] & 1 == 0 and c > 0:
			c -= 1
			L[i] ^= 1
		prod = prod % mod
		prod *= L[i] % mod
	print(prod % mod)


def solve(arr):
	ones = arr.count(1)
	temp = []
	for (i, x) in enumerate(arr):
		if x & 1 == 0:
			temp.append([x, i])
	temp.sort()
	for i in range(min(ones, len(temp))):
		arr[temp[i][1]] = 1
		arr.append(temp[i][0] + 1)
	mod = 998244353
	res = 1
	for i in arr:
		res = res * i % mod
	return res
t = int(input())
while t:
	n = int(input())
	arr = [int(i) for i in str(input()).split()]
	print(solve(arr))
	t -= 1


t = int(input())
while t:
	t -= 1
	n = int(input())
	x = list(map(int, input().split()))
	x.sort()
	k = x.count(1)
	c = 0
	for i in range(len(x)):
		if c == k:
			break
		if x[i] % 2 == 0:
			c += 1
			x[i] = x[i] + 1
	prod = 1
	for i in x:
		prod = prod % 998244353
		prod *= i % 998244353
	print(prod % 998244353)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	even = [i for i in a if i % 2 == 0]
	odd = [j for j in a if j % 2 == 1 and j != 1]
	even.sort()
	one = a.count(1)
	ans = 1
	for i in even:
		if one != 0:
			ans = ans * (i + 1)
			ans %= 998244353
			one -= 1
		else:
			ans = ans * i
			ans %= 998244353
	for j in odd:
		if j != 1:
			ans = ans * j % 998244353
	print(ans)


from enum import unique
import math

def calcGCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return abs(x)

def coprime(a, b):
	if calcGCD(a, b) == 1:
		print('Co-Prime')
	else:
		print('Not Co-Prime')

def countDivisibles(A, B, M):
	if A % M == 0:
		return B / M - A / M + 1
	return B / M - A / M

def max_cuts(n, a, b, c):
	if n == 0:
		return 0
	elif n < 0:
		return -1
	result = max(max_cuts(n - a, a, b, c), max_cuts(n - b, a, b, c), max_cuts(n - c, a, b, c))
	if result == -1:
		return -1
	return result + 1

def freq(list1):
	freq_count = {}
	for i in list1:
		if i in freq_count:
			freq_count[i] += 1
		else:
			freq_count[i] = 1
	return freq_count

def checker(arr, col):
	count = 0
	for i in range(8):
		for j in range(8):
			if arr[i][j] == str(col):
				count += 1
		if count == 8:
			return count
t = int(input())
for t1 in range(t):
	n = int(input())
	a1 = list(map(int, input().split(' ')))
	a = sorted(a1)
	onc = a.count(1)
	prod = 1
	mod = 998244353
	for i in range(n):
		if onc != 0 and a[i] % 2 == 0:
			onc -= 1
			prod = int(int(prod % mod) * (1 ^ a[i]) % mod)
		else:
			prod = int(int(prod % mod) * a[i] % mod)
	print(prod)


from collections import *
from math import *
from sys import *
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	mod = 998244353
	(eve, odd) = ([], [])
	cnt1 = 0
	for i in A:
		if i == 1:
			cnt1 += 1
		elif i % 2:
			odd.append(i)
		else:
			eve.append(i)
	val = 1
	eve.sort()
	for i in range(len(eve)):
		if cnt1 == 0:
			break
		eve[i] += 1
		cnt1 -= 1
	for i in eve:
		val = val * i % mod
	for i in odd:
		val = val * i % mod
	print(val % mod)


m = 998244353
t = int(input())
while t != 0:
	n = int(input())
	a = [int(i) for i in input().split()]
	x = 0
	s = 1
	b = []
	k = 1
	for i in a:
		if i == 1:
			x += 1
		elif i % 2 == 0:
			b.append(i)
		else:
			k = k * i
			k = k % m
	b.sort()
	for i in range(0, len(b)):
		if x > 0:
			k = k * (b[i] + 1)
			k = k % m
			x = x - 1
		else:
			k = k * b[i]
			k = k % m
	print(k)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	one = 0
	ans = 1
	for i in l:
		if i == 1:
			one += 1
	l.sort()
	for i in range(len(l)):
		if l[i] % 2 == 0 and one:
			l[i] += 1
			one -= 1
		ans = ans * l[i] % 998244353
	print(ans)


import sys
from math import *
from collections import defaultdict
input = sys.stdin.readline
mod = 998244353
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 1
	c = 0
	for i in range(n):
		if a[i] == 1:
			c += 1
	a.sort()
	for i in range(n):
		if a[i] % 2 == 0 and c > 0:
			a[i] ^= 1
			ans *= a[i]
			ans %= mod
			c -= 1
		else:
			ans *= a[i]
			ans %= mod
	print(ans)


MOD = 998244353
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	A = sorted(A)
	oneCount = A.count(1)
	for i in range(N):
		if A[i] % 2 == 0 and oneCount > 0:
			A[i] += 1
			oneCount -= 1
	ans = 1
	for a in A:
		ans = ans * a % MOD
	print(ans)


mod = 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	ct = l.count(1)
	res = 1
	i = 0
	while i < n:
		if ct > 0 and l[i] % 2 == 0:
			res = res * (l[i] + 1) % mod
			ct -= 1
		else:
			res = res * l[i] % mod
		i += 1
	print(res)


m = 998244353
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	count = arr.count(1)
	res = 1
	i = 0
	while i < n:
		if count > 0 and arr[i] % 2 == 0:
			res = res * (arr[i] + 1) % m
			count -= 1
		else:
			res = res * arr[i] % m
		i += 1
	print(res)


mod = 998244353
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	l.sort()
	ones = l.count(1)
	ans = 1
	x = 0
	len_even = 0
	while x < n:
		if l[x] % 2 == 0 and len_even < ones:
			ans *= l[x] ^ 1 % mod
			len_even += 1
		else:
			ans *= l[x] % mod
		ans %= mod
		x += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	p = 1
	c = 0
	b = []
	m = 998244353
	for i in arr:
		if i == 1:
			c += 1
		elif i & 1:
			p *= i
			p = p % m
		else:
			b.append(i)
	b.sort()
	for i in b:
		if c:
			p *= i ^ 1
			c -= 1
		else:
			p *= i
		p = p % m
	print(p)


from collections import Counter, defaultdict
import sys
import math

def sol(n, arr):
	ans = 1
	mod = 998244353
	ones = 0
	arr.sort()
	for i in range(n):
		if arr[i] == 1:
			ones += 1
		elif arr[i] % 2 == 0 and ones > 0:
			ones -= 1
			arr[i] += 1
		ans = ans * arr[i] % mod
	return ans
input = sys.stdin.readline

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

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

def insr():
	return str(input())

def invr():
	return map(int, input().split())
T = inp()
for i in range(T):
	n = inp()
	arr = inlt()
	print(sol(n, arr))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = sorted(list(map(int, input().split())))
	m = 998244353
	c = a.count(1)
	res = 1
	for i in a:
		if c > 0 and i % 2 == 0:
			i += 1
			c -= 1
		res = res * i % m
	print(res)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ones = arr.count(1)
	if ones == 0:
		product = 1
		for num in arr:
			product = product * num % 998244353
		print(product % 998244353)
	else:
		arr.sort()
		product = 1
		for num in arr:
			if num & 1 == 0 and ones > 0:
				product = product * (num + 1) % 998244353
				ones -= 1
			else:
				product = product * num % 998244353
		print(product % 998244353)


for ii in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(e, o) = ([], [])
	for i in range(n):
		if a[i] % 2 == 0:
			e.append(a[i])
		else:
			o.append(a[i])
	x = 0
	for i in range(n):
		if a[i] == 1:
			x += 1
	a.sort()
	ans = 1
	for i in range(n):
		if x == 0:
			break
		if a[i] % 2 == 0:
			a[i] += 1
			x -= 1
	for i in range(n):
		ans = ans * a[i] % 998244353
	print(ans)


for _ in range(int(input())):
	n = int(input())
	t = input().split()
	lis = []
	one_count = 0
	for i in t:
		if i == '1':
			one_count += 1
		lis.append(int(i))
	lis.sort()
	res = 1
	start = one_count
	for i in range(start, n):
		if one_count and lis[i] % 2 == 0:
			res = res * (lis[i] ^ 1) % 998244353
			one_count -= 1
		else:
			res = res * lis[i] % 998244353
	print(res)


def xorprod(lst):
	even = sorted([x for x in lst if x % 2 == 0])
	odd = sorted([x for x in lst if x % 2 == 1])
	i = j = 0
	while i < len(odd) and j < len(even):
		if odd[i] != 1:
			break
		even[j] += 1
		i += 1
		j += 1
	res = 1
	for i in range(len(odd)):
		res = res * odd[i] % 998244353
	for el in even:
		res = res * el % 998244353
	return res
T = int(input())
for t in range(T):
	n = int(input())
	lst = list(map(int, input().split()))
	print(xorprod(lst))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	c1 = a.count(1)
	for i in range(n):
		if a[i] % 2 == 0 and c1 > 0:
			a[i] += 1
			c1 -= 1
	r = 1
	for j in a:
		r = r % 998244353 * (j % 998244353) % 998244353
	print(r)


MODULO = 998244353
for _ in range(int(input())):
	n = int(input())
	a = list(map(lambda x: x % MODULO, map(int, input().split(' '))))
	e = [x for x in a if x % 2 == 0]
	o = 0
	for i in range(n):
		if a[i] == 1:
			o += 1
	e.sort()
	res = 1
	for x in e:
		res *= (x + (1 if o > 0 else 0)) % MODULO
		o -= 1
	for x in a:
		if x & 1:
			res *= x
			res %= MODULO
	print(res)


for T in range(int(input())):
	lent = int(input())
	l = [int(x) for x in input().split()]
	_1 = l.count(1)
	l_even = []
	odd_prod = 1
	for i in l:
		if i % 2 == 0:
			l_even.append(i % 998244353)
		else:
			odd_prod = odd_prod * i % 998244353
	l_even.sort()
	_even = len(l_even)
	if _even == 0:
		print(odd_prod % 998244353)
	else:
		if _1 >= _even:
			for i in range(_even):
				l_even[i] += 1
		else:
			for j in range(_1):
				l_even[j] += 1
		even_prod = 1
		for i in range(_even):
			even_prod = even_prod * l_even[i] % 998244353
		print(odd_prod % 998244353 * (even_prod % 998244353) % 998244353)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	ones = arr.count(1)
	prod = 1
	for i in arr:
		if ones > 0 and i % 2 == 0:
			prod = prod * (i + 1) % 998244353
			ones -= 1
		else:
			prod = prod * i % 998244353
	print(prod)


import os, sys, io, math
from re import *
from math import *
from array import *
from heapq import *
from bisect import *
from functools import *
from itertools import *
from statistics import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IP = lambda : map(int, input().split())
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
mod = 998244353
for _ in range(IN()):
	(n, l, res, c) = (IN(), I(), 1, 0)
	c = l.count(1)
	l.sort()
	for i in range(n):
		if l[i] == 1:
			continue
		if l[i] % 2 == 0:
			if c > 0:
				c -= 1
				l[i] += 1
		res = res % mod * (l[i] % mod) % mod
	print(res % mod)


t = int(input())
for p in range(t):
	temp = 0
	count = 0
	l = []
	m = []
	n = int(input())
	a = input()
	a = a.split(' ')
	for i in range(n):
		a[i] = int(a[i])
		if a[i] == 1:
			count += 1
		if a[i] % 2 == 0:
			m.append(a[i])
		else:
			l.append(a[i])
	m.sort()
	k = len(m)
	while count > 0 and k > 0:
		m[temp] = m[temp] + 1
		count = count - 1
		temp = temp + 1
		k = k - 1
	l.extend(m)
	prod = 1
	for i in range(n):
		prod = prod * l[i] % 998244353
	print(prod)


m = 998244353
t = int(input())
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	q = a.count(1)
	a.sort()
	ans = 1
	for r in a:
		if r & 1 == 0 and q != 0:
			ans = ans * ((r + 1) % m) % m
			q -= 1
		else:
			ans = ans * (r % m) % m
	print(ans)


mod = 998244353
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	count = arr.count(1)
	ans = 1
	for i in range(n):
		if arr[i] % 2 == 0 and count > 0:
			arr[i] = arr[i] + 1
			count -= 1
		ans = ans * arr[i] % mod
	print(ans)


from bisect import bisect_left
from bisect import bisect_right
from getopt import getopt
import re
from tempfile import tempdir
from traceback import print_tb
from typing import DefaultDict
import math
from collections import Counter, defaultdict
from math import sqrt
import collections
from sys import maxsize
from itertools import combinations_with_replacement
import copy
import heapq
from collections import deque
import sys

def sieve_erasthones(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	return prime

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def count_factors(n):
	i = 1
	c = 0
	ans = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				c += 1
				ans.append(n // i)
			else:
				c += 2
				ans.append(i)
				ans.append(n // i)
		i += 1
	return ans

def ncr_modulo(n, r, p):
	num = 2
	den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def modular_exponentiation(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 != 0:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def number_of_primefactor(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
	return l

def twosum(a, n, x):
	rem = []
	for i in range(x):
		rem.append(0)
	for i in range(n):
		if a[i] < x:
			rem[a[i] % x] += 1
	for i in range(1, x // 2):
		if rem[i] > 0 and rem[x - i] > 0:
			return True
	if i >= x // 2:
		if x % 2 == 0:
			if rem[x // 2] > 1:
				return True
			else:
				return False
		elif rem[x // 2] > 0 and rem[x - x // 2] > 0:
			return True
		else:
			return False

def divSum(num):
	result = 0
	i = 2
	while i <= math.sqrt(num):
		if num % i == 0:
			if i == num / i:
				result = result + i
			else:
				result = result + (i + num / i)
		i = i + 1
	return result + 1 + num

def subsequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def primeFactors(n):
	d = defaultdict(lambda : 0)
	while n % 2 == 0:
		d[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[int(i)] += 1
			n = n / i
	if n > 2:
		d[int(n)] += 1
	return d

def lcm(a, b):
	return a * b // math.gcd(a, b)

def modInverse(b, m):
	return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def gcdList(l):
	a = l[0]
	for i in range(1, len(l)):
		a = math.gcd(a, l[i])
	return a

def solve(t):
	n = int(input())
	mod = 998244353
	l = list(map(int, input().split()))
	even = []
	ans = 1
	curr = 0
	for ele in l:
		if ele % 2 == 0:
			even.append(ele)
		elif ele == 1:
			curr += 1
		else:
			ans *= ele
			ans %= mod
	even.sort()
	bool = True
	for ele in even:
		if curr == 0:
			ans *= ele
			ans %= mod
		elif bool:
			ans *= ele + 1
			ans %= mod
			curr -= 1
	return ans
for t in range(1, int(input()) + 1):
	print(solve(t))


mod = 998244353

def max_xor_product(n, a):
	(evens, odds) = (sorted([x for x in a if x % 2 == 0]), sorted([x for x in a if x % 2 == 1]))
	p = q = 0
	while p < len(odds) and q < len(evens):
		if odds[p] != 1:
			break
		evens[q] += 1
		p += 1
		q += 1
	ans = 1
	for i in range(p, len(odds)):
		ans = ans * odds[i] % mod
	for x in evens:
		ans = ans * x % mod
	print(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	max_xor_product(n, a)


def solution():
	n = int(input())
	a = [int(num) for num in input().split()]
	mod = 998244353
	ones = []
	evens = []
	others = []
	ans = 1
	for num in a:
		if num == 1:
			ones.append(1)
		elif num % 2 == 0:
			evens.append(num)
		else:
			others.append(num)
	n = min(len(ones), len(evens))
	evens.sort()
	for i in range(n):
		ans = ans * (evens[i] + 1) % mod
	for i in range(n, len(evens)):
		ans = ans * evens[i] % mod
	for num in others:
		ans = ans * num % mod
	print(ans)

def main():
	t = int(input())
	while t:
		solution()
		t -= 1
main()


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	c = l.count(1)
	l.sort()
	ans = 1
	for i in range(n):
		if l[i] % 2 == 0 and c > 0:
			ans *= l[i] + 1
			ans %= 998244353
			c -= 1
		else:
			ans *= l[i]
			ans %= 998244353
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	one = 0
	for i in range(n):
		if a[i] == 1:
			one += 1
		else:
			break
	j = 0
	ans = 1
	for elem in a:
		if one > 0 and elem % 2 == 0:
			ans *= elem + 1
			ans %= 998244353
			one -= 1
		else:
			ans *= elem
			ans %= 998244353
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 1
	mod = 998244353
	ev = []
	ctr = 0
	for i in range(n):
		if arr[i] == 1:
			ctr += 1
		elif arr[i] % 2 == 0:
			ev.append(arr[i])
		else:
			ans *= arr[i]
			ans %= mod
	ev.sort()
	for i in range(len(ev)):
		if ctr != 0:
			ans *= ev[i] + 1
			ctr -= 1
			ans %= mod
		else:
			ans *= ev[i]
			ans %= mod
	print(ans % mod)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	e = []
	o = []
	c = 0
	for i in arr:
		if i == 1:
			c += 1
		elif i % 2 == 0:
			e.append(i)
		else:
			o.append(i)
	p = 1
	for i in o:
		p = p * i % 998244353
	e.sort()
	for i in e:
		elem = i
		if c > 0:
			elem += 1
			c -= 1
		p = p * elem % 998244353
	print(p)


t = int(input())
while t != 0:
	m = 998244353
	n = int(input())
	a = list(map(int, input().split()))
	count1 = a.count(1)
	a.sort()
	u = 1
	for i in range(n):
		if a[i] % 2 == 0 and count1 > 0:
			a[i] += 1
			u = u * a[i] % m
			count1 -= 1
		else:
			u = u * a[i] % m
	print(u % m)
	t -= 1


n = int(input())
for i in range(n):
	le = int(input())
	arr = [int(x) for x in input().split()]
	one = []
	even = []
	prod = 1
	for k in range(le):
		if arr[k] == 1:
			one.append(1)
		elif arr[k] % 2 == 1:
			prod = prod * arr[k] % 998244353
		else:
			even.append(arr[k])
	l = len(one)
	e = len(even)
	if l == 0:
		for k in range(e):
			prod = prod * even[k] % 998244353
		print(prod)
	elif l >= e:
		for k in range(e):
			prod = prod * (even[k] + 1) % 998244353
		print(prod)
	else:
		even.sort()
		for k in range(l):
			prod = prod * (even[k] + 1) % 998244353
		for k in range(l, e):
			prod = prod * even[k] % 998244353
		print(prod)


import bisect
import math
import sys
from collections import Counter, deque
import re
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = [int(i) for i in sys.stdin.readline().split()]
	ans = 1
	a.sort()
	one = a.count(1)
	for i in range(0, n):
		if one > 0 and a[i] % 2 == 0:
			a[i] += 1
			one -= 1
		if one == 0:
			break
	for j in a:
		ans = ans * j % 998244353
	print(ans)


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	lst.sort()
	c = lst.count(1)
	for i in range(len(lst)):
		if c > 0 and lst[i] % 2 == 0 and (lst[i] != 1):
			lst[i] += 1
			c -= 1
	ans = 1
	for i in lst:
		ans = ans * i % 998244353
	print(ans)


for t in range(int(input())):
	l = int(input())
	l1 = [int(i) for i in input().split()]
	l1.sort()
	c = 0
	mod = 998244353
	c = l1.count(1)
	ans = 1
	for i in range(c, l):
		if l1[i] % 2 == 0 and c > 0:
			l1[i] += 1
			c -= 1
		if c <= 0:
			break
	if l == 0:
		ans = 0
	else:
		for k in range(l):
			ans = ans * l1[k] % 998244353
	print(ans % 998244353)


t = int(input())
MOD = 998244353
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	odd = []
	even = []
	for x in arr:
		if x % 2 == 1:
			odd.append(x)
		else:
			even.append(x)
	even.sort()
	c = arr.count(1)
	ans = 1
	for x in even:
		if c == 0:
			ans = ans * x % MOD
		else:
			ans = ans * (x + 1) % MOD
			c -= 1
	for x in odd:
		ans = ans * x % MOD
	print(ans % 998244353)


def xorprod(a):
	c1 = a.count(1)
	even = []
	odd = []
	for e in a:
		if e & 1 == 0:
			even.append(e)
		else:
			odd.append(e)
	even.sort()
	for i in range(min(c1, len(even))):
		even[i] = (even[i] ^ 1) % 998244353
	p = 1
	for e in even:
		p = p * e % 998244353
	for o in odd:
		p = p * o % 998244353
	return p
import math as mm
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(xorprod(a))


import numpy as np
T = int(input())
for _ in range(T):
	N = int(input())
	A = sorted([int(i) for i in input().split()])
	sum_1 = A.count(1)
	for i in range(len(A)):
		if sum_1 != 0 and A[i] % 2 == 0 and (A[i] != 1):
			A[i] += 1
			sum_1 -= 1
	s = 1
	for i in A:
		s = s * i % 998244353
	print(s)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	b = []
	for i in a:
		if i == 1:
			b.append(1)
		else:
			break
	for i in b:
		del a[0]
	if len(a) == 0:
		print(1)
		continue
	a.sort(reverse=True, key=lambda x: (1 ^ x) / x)
	for i in range(min(len(b), len(a))):
		if 1 ^ a[i] < a[i]:
			break
		a[i] = 1 ^ a[i]
	v = 1
	for i in a:
		v = v * i % 998244353
	print(v)


t = int(input())
for i in range(t):
	n = int(input())
	l = list([int(x) for x in input().split()])
	oc = 0
	ll = []
	for i in l:
		if i > 0:
			if i == 1:
				oc = oc + 1
			else:
				ll.append(i)
	ll = sorted(ll)
	for i in range(0, len(ll)):
		if oc == 0:
			break
		if ll[i] % 2 == 0:
			ll[i] = ll[i] + 1
			oc = oc - 1
	ans = 1
	for i in ll:
		ans = ans * i % 998244353
	print(ans)


m = 998244353
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = 1
	ones = 0
	one_inv = []
	for e in a:
		if e > 1:
			if e & 1 == 0:
				one_inv.append(e)
			else:
				p *= e
				p %= m
		elif e == 1:
			ones += 1
	one_inv.sort()
	for e in one_inv[:ones]:
		p *= e + 1
		p %= m
	for e in one_inv[ones:]:
		p *= e
		p %= m
	print(p)


for _ in range(int(input())):
	N = int(input())
	A = [int(a) for a in input().split()]
	even = []
	odd = []
	for i in range(N):
		if A[i] % 2 == 0:
			even.append(A[i])
		else:
			odd.append(A[i])
	count = odd.count(1)
	even = sorted(even)
	j = 0
	curr = 0
	while curr < len(even) and j < count:
		even[curr] += 1
		j += 1
		curr += 1
	mod = 998244353
	value = 1
	for i in range(len(odd)):
		value = value * odd[i]
		value = value % mod
	for i in range(len(even)):
		value = value * even[i]
		value = value % mod
	print(value)


from collections import defaultdict
import math as mt
mod = 998244353
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	odd = []
	even = []
	one = 0
	for i in a:
		if i & 1:
			if i == 1:
				one += 1
			else:
				odd.append(i)
		else:
			even.append(i)
	even.sort(reverse=True)
	k = len(even) - 1
	while one > 0 and k >= 0:
		even[k] ^= 1
		k -= 1
		one -= 1
	ans = 1
	for i in odd:
		ans = ans % mod * (i % mod) % mod
	for i in even:
		ans = ans % mod * (i % mod) % mod
	print(ans)


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	a = []
	m = 1
	for i in l:
		if i == 1:
			c += 1
	l.sort()
	i = 0
	for i in range(n):
		if l[i] % 2 == 0 and c > 0:
			c -= 1
			l[i] += 1
	for i in l:
		m = m * i % 998244353
	print(m)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	count = l.count(1)
	l.sort()
	for i in range(n):
		if l[i] != 1 and l[i] % 2 == 0 and (count > 0):
			l[i] += 1
			count -= 1
	s = 1
	for i in range(n):
		s = s * l[i] % 998244353
	print(s)


t = int(input())
for i in range(t):
	l = int(input())
	lis = list(map(int, input().split()))
	c = lis.count(1)
	res = sorted(lis)
	ans = 1
	for i in range(len(res)):
		if c > 0 and res[i] % 2 == 0:
			ans = ans % 998244353 * ((res[i] + 1) % 998244353) % 998244353
			c -= 1
		else:
			ans = ans % 998244353 * (res[i] % 998244353) % 998244353
	print(ans % 998244353)