package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

const MOD int64 = 998244353
const MAXN = 5000

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) NextInt() int {
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if (c >= '0' && c <= '9') || c == '-' {
			break
		}
		fs.idx++
	}
	sign := 1
	if fs.idx < fs.n && fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if c < '0' || c > '9' {
			break
		}
		val = val*10 + int(c-'0')
		fs.idx++
	}
	return sign * val
}

func modPow(a, e int64) int64 {
	res := int64(1)
	for e > 0 {
		if e&1 == 1 {
			res = res * a % MOD
		}
		a = a * a % MOD
		e >>= 1
	}
	return res
}

var fact [MAXN + 1]int64
var invFact [MAXN + 1]int64

func comb(n, k int) int64 {
	if k < 0 || k > n || n < 0 {
		return 0
	}
	return fact[n] * invFact[k] % MOD * invFact[n-k] % MOD
}

func eligible(s, m int) int {
	if s == 0 {
		return 0
	}
	if s == m {
		return m
	}
	return s - 1
}

func main() {
	fact[0] = 1
	for i := 1; i <= MAXN; i++ {
		fact[i] = fact[i-1] * int64(i) % MOD
	}
	invFact[MAXN] = modPow(fact[MAXN], MOD-2)
	for i := MAXN; i >= 1; i-- {
		invFact[i-1] = invFact[i] * int64(i) % MOD
	}

	fs := NewFastScanner()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	t := fs.NextInt()
	for ; t > 0; t-- {
		n := fs.NextInt()
		m := n / 2

		counts := make([]int, 0, n)
		prev := -1
		cnt := 0
		for i := 0; i < n; i++ {
			x := fs.NextInt()
			if i == 0 || x != prev {
				if i > 0 {
					counts = append(counts, cnt)
				}
				prev = x
				cnt = 1
			} else {
				cnt++
			}
		}
		counts = append(counts, cnt)

		dp := make([]int64, m+1)
		dp[0] = 1
		totalAbove := 0

		for i := len(counts) - 1; i >= 0; i-- {
			c := counts[i]
			ndp := make([]int64, m+1)
			for s := 0; s <= m; s++ {
				cur := dp[s]
				if cur == 0 {
					continue
				}
				rem := eligible(s, m) - (totalAbove - s)
				for x := 0; x <= 1 && x <= c && s+x <= m; x++ {
					d := c - x
					if d > rem {
						continue
					}
					ways := comb(rem, d)
					ndp[s+x] += cur * ways % MOD
					if ndp[s+x] >= MOD {
						ndp[s+x] -= MOD
					}
				}
			}
			dp = ndp
			totalAbove += c
		}

		fmt.Fprintln(out, dp[m]%MOD)
	}
}