Rusty String


题意 多组数据,每次给一个由 'V','K','?' 三种字符构成的字符串,你需要把所有为 '?' 的位置填成 'V' 或者 'K' ,你要求出所有最终构造出来的字符串里所有可行的周期,我们称$i$为字符串$S$的周期当且仅当$S$向右平移$i$位之后和原串重叠的部分完全一样,例如 "VKKVK" ,当$i=3$时: ```cpp VKKVK VKKVK ``` 它们重叠的部分都是 "VK" ,所以3是一个周期,同理5也是一个周期(重叠部分为空也可以)。 输出答案时,要先输出一行一个数为你求得的所有可行周期的个数,接下来一行按照**升序**输出所有的可行周期。 保证输入字符串总长不超过$5*10^5$。


Grigory loves strings. Recently he found a metal strip on a loft. The strip had length $ n $ and consisted of letters "V" and "K". Unfortunately, rust has eaten some of the letters so that it's now impossible to understand which letter was written. Grigory couldn't understand for a long time what these letters remind him of, so he became interested in the following question: if we put a letter "V" or "K" on each unreadable position, which values can the period of the resulting string be equal to? A period of a string is such an integer $ d $ from $ 1 $ to the length of the string that if we put the string shifted by $ d $ positions to the right on itself, then all overlapping letters coincide. For example, $ 3 $ and $ 5 $ are periods of "VKKVK".



There are several (at least one) test cases in the input. The first line contains single integer — the number of test cases. There is an empty line before each test case. Each test case is described in two lines: the first line contains single integer $ n $ ( $ 1<=n<=5·10^{5} $ ) — the length of the string, the second line contains the string of length $ n $ , consisting of letters "V", "K" and characters "?". The latter means the letter on its position is unreadable. It is guaranteed that the sum of lengths among all test cases doesn't exceed $ 5·10^{5} $ . For hacks you can only use tests with one test case.


For each test case print two lines. In the first line print the number of possible periods after we replace each unreadable letter with "V" or "K". In the next line print all these values in increasing order.


输入样例 #1


输出样例 #1

3 5
1 2 3 4 5 6
2 3 4


In the first test case from example we can obtain, for example, "VKKVK", which has periods $ 3 $ and $ 5 $ . In the second test case we can obtain "VVVVVV" which has all periods from $ 1 $ to $ 6 $ . In the third test case string "KVKV" has periods $ 2 $ and $ 4 $ , and string "KVKK" has periods $ 3 $ and $ 4 $ .