#include <cstdio>
#include <algorithm>

const int mod = 998244353;
int a[1000005], n;
char s[1000005];

int main() {
	int _; scanf("%d", &_);
	while (_ --) {
		scanf("%d%s", &n, s + 1), n <<= 1;
		if (n == 2) {puts("1"); continue;}
		int ans = 748683265, w0 = 1, w1 = 1, b0 = 0, b1 = 0;
		for (int i = 2; i <= n; ++ i)
			if (s[i] == s[1]) {//w0,b0 w1,b1
				if (w0 && w1) ++ w0, ++ w1;
				else if (w0 && b1) -- b1, ++ w1;
				else if (b0 && w1) -- b0, ++ w0;
				else if (b0 && b1) {
					if (b0 == 1) ans = 2ll * ans % mod, -- b0, ++ w0;
					else ans = 1ll * ans * b0 % mod * (b0 - 1) % mod, -- b0, -- b1;
				}
			} else {
				if (b0 && b1) ++ b0, ++ b1;
				else if (b0 && w1) -- w1, ++ b1;
				else if (w0 && b1) -- w0, ++ b0;
				else if (w0 && w1) {
					if (w0 == 1) ans = 2ll * ans % mod, -- w0, ++ b0;
					else ans = 1ll * ans * w0 % mod * (w0 - 1) % mod, -- w0, -- w1;
				}
			}
		printf("%d\n", ans);
	}
	return 0;
}