E. Ржавая строка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Григорий увлекается строками. Недавно он нашел на чердаке металлическую полоску со строкой длины 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.