格里戈里喜欢弦乐。最近他在阁楼上发现了一条金属条。该条带的长度为n,由字母“V”和“K”组成。不幸的是,锈蚀已经腐蚀了一些字母,因此现在无法理解写的是哪一个字母。
格里戈里很长一段时间都无法理解这些字母让他想起了什么,于是他对以下问题产生了兴趣:如果我们在每个不可读的位置上放置一个字母“V”或“K”,得到的字符串的周期可以等于哪些值?
字符串的周期是从 1 到字符串长度的整数 d,如果我们将字符串向右移动 d 个位置,则所有重叠的字母都会重合。例如,3和5是“VKKVK”的周期。
输入
输入中有多个(至少一个)测试用例。第一行包含单个整数——测试用例的数量。
每个测试用例之前都有一个空行。每个测试用例由两行描述:第一行包含单个整数 n (1 ≤ n ≤ 5·105) - 字符串的长度,第二行包含长度为 n 的字符串,由字母“V”、“K”和字符“?”组成。后者意味着其位置上的字母不可读。
保证所有测试用例的长度之和不超过5·105。
对于 hacks,您只能使用一个测试用例进行测试。
输出
对于每个测试用例,打印两行。在第一行中,在我们用“V”或“K”替换每个不可读的字母后,打印可能的句点数。在下一行中按升序打印所有这些值。
示例
输入 #1
3 5 V??VK 6 ?????? 4 ?VK?
输出 #1
2 3 5 6 1 2 3 4 5 6 3 2 3 4
注意
在示例的第一个测试用例中,我们可以获得例如“VKKVK”,它具有周期 3 和 5。
在第二个测试用例中,我们可以获得“VVVVVV”,它具有从 1 到 6 的所有周期。
在第三个测试用例中,字符串“KVKV”具有周期 2 和 4,字符串“KVKK”具有周期 3 和 4。