{"raw_statement":[{"iden":"statement","content":"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.\n\nGrigory 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?\n\nA 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_\"."},{"iden":"input","content":"There are several (at least one) test cases in the input. The first line contains single integer — the number of test cases.\n\nThere 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·105) — 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.\n\nIt is guaranteed that the sum of lengths among all test cases doesn't exceed 5·105.\n\n**For hacks** you can only use tests with one test case."},{"iden":"output","content":"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."},{"iden":"example","content":"Input\n\n3\n \n5\nV??VK\n \n6\n??????\n \n4\n?VK?\n\nOutput\n\n2\n3 5\n6\n1 2 3 4 5 6\n3\n2 3 4"},{"iden":"note","content":"In the first test case from example we can obtain, for example, \"_VKKVK_\", which has periods 3 and 5.\n\nIn the second test case we can obtain \"_VVVVVV_\" which has all periods from 1 to 6.\n\nIn the third test case string \"_KVKV_\" has periods 2 and 4, and string \"_KVKK_\" has periods 3 and 4."}],"translated_statement":[{"iden":"statement","content":"Grigory 爱好字符串。最近他在阁楼上发现了一条金属条，其长度为 $n$，由字母 \"_V_\" 和 \"_K_\" 组成。不幸的是，锈蚀损坏了一些字母，现在无法分辨原来写的是哪个字母。\n\nGrigory 长时间思考这些字母让他想起了什么，于是他产生了以下问题：如果我们在每个不可读的位置填入 \"_V_\" 或 \"_K_\"，那么所得字符串的周期可能取哪些值？\n\n一个字符串的周期是指一个整数 $d$（从 $1$ 到字符串长度），使得将该字符串向右平移 $d$ 个位置后与原字符串重叠时，所有重叠位置的字母完全一致。例如，$3$ 和 $5$ 都是字符串 \"_VKKVK_\" 的周期。\n\n输入包含多个（至少一个）测试用例。第一行包含一个整数 —— 测试用例的数量。\n\n每个测试用例前有一行空行。每个测试用例由两行描述：第一行包含一个整数 $n$（$1 ≤ n ≤ 5·10^5$）—— 字符串的长度；第二行包含一个长度为 $n$ 的字符串，由字母 \"_V_\"、\"_K_\" 和字符 \"_?_\" 组成，其中 \"_?_\" 表示该位置的字母不可读。\n\n保证所有测试用例的字符串长度总和不超过 $5·10^5$。\n\n*对于 Hack*，你只能使用包含一个测试用例的测试数据。\n\n对于每个测试用例，输出两行。第一行输出在将每个不可读字母替换为 \"_V_\" 或 \"_K_\" 后，可能的周期数量；第二行按升序输出所有这些周期值。\n\n在示例的第一个测试用例中，我们可以得到例如 \"_VKKVK_\"，其周期为 $3$ 和 $5$。\n\n在第二个测试用例中，我们可以得到 \"_VVVVVV_\"，其周期为从 $1$ 到 $6$ 的所有整数。\n\n在第三个测试用例中，字符串 \"_KVKV_\" 的周期为 $2$ 和 $4$，而字符串 \"_KVKK_\" 的周期为 $3$ 和 $4$。"},{"iden":"input","content":"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 #cf_span[n] (#cf_span[1 ≤ n ≤ 5·105]) — the length of the string, the second line contains the string of length #cf_span[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 #cf_span[5·105].*For hacks* you can only use tests with one test case."},{"iden":"output","content":"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."},{"iden":"note","content":"In the first test case from example we can obtain, for example, \"_VKKVK_\", which has periods #cf_span[3] and #cf_span[5].In the second test case we can obtain \"_VVVVVV_\" which has all periods from #cf_span[1] to #cf_span[6].In the third test case string \"_KVKV_\" has periods #cf_span[2] and #cf_span[4], and string \"_KVKK_\" has periods #cf_span[3] and #cf_span[4]."}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the string.  \nLet $ S = s_1 s_2 \\dots s_n $ be a string over alphabet $ \\{V, K, ?\\} $, where $ ? $ denotes an unknown character.  \nLet $ \\Sigma = \\{V, K\\} $.  \nFor each position $ i $ with $ s_i = ? $, assign $ s_i \\in \\Sigma $ arbitrarily.  \nLet $ \\mathcal{S} $ be the set of all possible strings obtained by replacing each $ ? $ with $ V $ or $ K $.  \n\nFor a string $ T \\in \\mathcal{S} $, define its period set $ P(T) = \\{ d \\in \\mathbb{Z}^+ \\mid 1 \\le d \\le n \\text{ and } T[i] = T[i + d] \\text{ for all } i \\text{ such that } 1 \\le i \\le n - d \\} $.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 5 \\cdot 10^5 $  \n2. The total sum of $ n $ across all test cases $ \\le 5 \\cdot 10^5 $  \n3. Each $ s_i \\in \\{V, K, ?\\} $  \n\n**Objective**  \nFor each test case, compute the set $ \\mathcal{P} = \\bigcup_{T \\in \\mathcal{S}} P(T) $, i.e., all integers $ d \\in [1, n] $ such that there exists at least one completion $ T \\in \\mathcal{S} $ for which $ d $ is a period of $ T $.  \nOutput $ |\\mathcal{P}| $ and the elements of $ \\mathcal{P} $ in increasing order.","simple_statement":null,"has_page_source":false}