给定一个由小写字母和 ? 组成的字符串，? 可以表示任意小写字母。你需要是将这个字符串分割成尽可能少的回文子串。求出最少可以分割成多少个回文子串，并计算填充所有 ? 后再分割的方案数，两种方案不同当且仅当填充 ? 的方式不同或者划分序列的方式不同。最终的分割方案数需要对 998244353 取模后输出。
对于两个长度均为 k 的分割序列 [s1,s2,…,sk] 和 [t1,t2,…,tk] 来说，称它们不同当且仅当存在一个下标 i(1≤i≤k)，使得 si=ti。
对于一个长度为 n 的字符串 s 来说，s 的一个子串为存在两个下标 l,r(1≤l≤r≤∣s∣)，那么 sl…sr 就是 s 的一个子串。例如字符串 "abc" 的子串有 "a","b","c","ab","bc","abc"，但是 "ac","cb","ba","d" 都不是字符串 "abc" 的子串。
如果一个字符串从前向后读和从后向前读得到的序列是一样的，那么这个字符串就是一个回文串。例如，"madam" 和 "racecar" 都是回文串，但是 "love" 和 "seu" 都不是回文串。
对于 k 个字符串 [s1,s2,…,sk] 来说，把它们按顺序拼接起来得到的结果为 s1+s2+⋯+sk，例如 "a"+"bb"+"ccc"="abbccc"。
第一行，一个整数 t(1≤t≤5000)，代表数据组数。
对于每组数据：
第一行，一个整数 n(1≤n≤5000)，代表字符串的长度。
第二行，一个长度为 n 的仅由小写字母和 ? 组成的字符串 s。
保证同一测试点内 n 的总和不超过 5000。
对于每组数据，输出共两行。第一行，两个整数 k,c(1≤k≤n;0≤c≤998244352)，代表拆分出的字符串的数量和在把字符串拆分成 k 部分的且填充所有 ? 情况下，划分方案数是多少；第二行 k 个用空格隔开的字符串 s1,…,sk，代表拆分出的字符串，需要满足这些字符串全都是回文串且 s1+⋯+sk=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