J. 我喜欢回文串
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

Input

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

对于每组数据：

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

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

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

Output

对于每组数据，输出共两行。第一行，两个整数 $$$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$$$，输出任意一种合法的划分方案即可。

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

Example
Input
4
5
lyljl
5
?yj?y
6
aazzaa
7
aa??zaa
Output
3 2
l y ljl 
1 1
yyjyy 
1 1
aazzaa 
1 26
aazazaa