Григорий увлекается строками. Недавно он нашел на чердаке металлическую полоску со строкой длины n из букв «V» и «K». К сожалению, ржавчина съела некоторые из символов, и теперь невозможно понять, какая из букв была там написана.
Григорий никак не мог понять, что же ему напоминают эти буквы, и ему стало интересно: если на месте каждого неразличимого символа поставить букву «V» или букву «K», какие значения сможет принимать период строки?
Период строки — такое целое число d от 1 до длины строки, что, если на строку наложить ее же, сдвинутую на d вправо, то все накладывающиеся символы совпадут. Например, 3 и 5 — периоды строки VKKVK.
Во входных данных находятся несколько (не меньше одного) тестовых случаев. В первой строке находится одно целое число — количество тестовых случаев.
Перед данными для каждого тестового случая идет пустая строка. Данные тестового случая описываются в двух строках: в первой находится одно целое число n (1 ≤ n ≤ 5·105) — длина строки, а во второй — сама строка длины n, состоящая из символов «V», «K» и «?». Последний из них обозначает неразличимый символ.
Гарантируется, что сумма длин строк во всех тестовых случаях не превосходит 5·105.
Для взломов разрешается использовать только тесты с одним тестовым случаем.
Для каждого тестового случая выведите две строки. В первой выведите количество различных значений, которые может принимать период строки, если каждый неразличимый символ заменить на «V» или «K». В следующей строке выведите все эти значения в возрастающем порядке.
3
5
V??VK
6
??????
4
?VK?
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.
Название |
---|