#542. 我喜欢回文串

给定一个由小写字母和 $?$ 组成的字符串，$?$ 可以表示任意小写字母。你需要是将这个字符串分割成尽可能少的回文子串。求出最少可以分割成多少个回文子串，并计算填充所有 $?$ 后再分割的方案数，两种方案不同当且仅当填充 $?$ 的方式不同或者划分序列的方式不同。最终的分割方案数需要对 $998244353$ 取模后输出。

对于两个长度均为 $k$ 的分割序列 $[s_1,s_2,\dots,s_k]$ 和 $[t_1,t_2,\dots,t_k]$ 来说，称它们不同当且仅当存在一个下标 $i(1\le i\le k)$，使得 $s_i\neq t_i$。

对于一个长度为 $n$ 的字符串 $s$ 来说，$s$ 的一个子串为存在两个下标 $l,r(1\le l\le r\le |s|)$，那么 $s_l\dots s_r$ 就是 $s$ 的一个子串。例如字符串 $"abc"$ 的子串有 $"a","b","c","ab","bc","abc"$，但是 $"ac","cb","ba","d"$ 都不是字符串 $"abc"$ 的子串。

如果一个字符串从前向后读和从后向前读得到的序列是一样的，那么这个字符串就是一个回文串。例如，$"madam"$ 和 $"racecar"$ 都是回文串，但是 $"love"$ 和 $"seu"$ 都不是回文串。

对于 $k$ 个字符串 $[s_1,s_2,\dots,s_k]$ 来说，把它们按顺序拼接起来得到的结果为 $s_1+s_2+\dots+s_k$，例如 $"a"+"bb"+"ccc"="abbccc"$。

第一行，一个整数 $t(1\le t\le 5000)$，代表数据组数。

对于每组数据：

第一行，一个整数 $n(1\le n \le 5000)$，代表字符串的长度。

第二行，一个长度为 $n$ 的仅由小写字母和 $?$ 组成的字符串 $s$。

保证同一测试点内 $n$ 的总和不超过 $5000$。

对于每组数据，输出共两行。第一行，两个整数 $k,c(1\le k\le n;0\le c\le 998244352)$，代表拆分出的字符串的数量和在把字符串拆分成 $k$ 部分的且填充所有 $?$ 情况下，划分方案数是多少；第二行 $k$ 个用空格隔开的字符串 $s_1,\dots,s_k$，代表拆分出的字符串，需要满足这些字符串全都是回文串且 $s_1+\dots+s_k=s$，输出任意一种合法的划分方案即可。

任何满足题目要求的答案都是正确的。

输入样例

4
5
lyljl
5
?yj?y
6
aazzaa
7
aa??zaa

输出样例

3 2
l y ljl 
1 1
yyjyy 
1 1
aazzaa 
1 26
aazazaa