{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eFor each prefix of a given string \u003cb\u003e\u003ci\u003eS \u003c/i\u003e\u003c/b\u003ewith \u003cb\u003e\u003ci\u003eN \u003c/i\u003e\u003c/b\u003echaracters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each \u003cb\u003e\u003ci\u003ei \u003c/i\u003e\u003c/b\u003e(2 \u0026lt;\u003d \u003cb\u003e\u003ci\u003ei \u003c/i\u003e\u003c/b\u003e \u0026lt;\u003d \u003cb\u003e\u003ci\u003eN\u003c/i\u003e\u003c/b\u003e) we want to know the largest \u003cb\u003e\u003ci\u003eK \u003c/i\u003e\u003c/b\u003e\u0026gt; 1 (if there is one) such that the prefix of \u003cb\u003e\u003ci\u003eS \u003c/i\u003e\u003c/b\u003ewith length \u003cb\u003e\u003ci\u003ei \u003c/i\u003e\u003c/b\u003ecan be written as \u003cb\u003e\u003ci\u003eA\u003c/i\u003e\u003csup\u003e\u003cfont size\u003d\"+1\"\u003e\u003ci\u003eK \u003c/i\u003e\u003c/font\u003e\u003c/sup\u003e\u003cfont size\u003d\"+1\"\u003e\u003cfont size\u003d\"+1\"\u003e\u003c/font\u003e\u003c/font\u003e\u003c/b\u003e\u003cfont size\u003d\"+1\"\u003e\u003cfont size\u003d\"+1\"\u003e, that is \u003cb\u003e\u003ci\u003eA \u003c/i\u003e\u003c/b\u003econcatenated \u003cb\u003e\u003ci\u003eK \u003c/i\u003e\u003c/b\u003etimes, for some string \u003cb\u003e\u003ci\u003eA\u003c/i\u003e\u003c/b\u003e. Of course, we also want to know the period \u003cb\u003e\u003ci\u003eK\u003c/i\u003e\u003c/b\u003e. \u003c/font\u003e\u003c/font\u003e\u003c/p\u003e\u003cfont size\u003d\"+1\"\u003e\u003cfont size\u003d\"+1\"\u003e\n\u003cp\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eThe input file consists of several test cases. Each test case consists of two lines. The first one contains \u003cb\u003e\u003ci\u003eN \u003c/i\u003e\u003c/b\u003e(2 \u0026lt;\u003d \u003cb\u003e\u003ci\u003eN \u003c/i\u003e\u003c/b\u003e\u0026lt;\u003d 1 000 000) – the size of the string \u003cb\u003e\u003ci\u003eS\u003c/i\u003e\u003c/b\u003e. The second line contains the string \u003cb\u003e\u003ci\u003eS\u003c/i\u003e\u003c/b\u003e. The input file ends with a line, having the number zero on it. \u003c/p\u003e\n\u003cp\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eFor each test case, output “Test case #” and the consecutive test case number on a single line; then, for each prefix with length \u003cb\u003e\u003ci\u003ei \u003c/i\u003e\u003c/b\u003ethat has a period \u003cb\u003e\u003ci\u003eK \u003c/i\u003e\u003c/b\u003e\u0026gt; 1, output the prefix size \u003cb\u003e\u003ci\u003ei \u003c/i\u003e\u003c/b\u003eand the period \u003cb\u003e\u003ci\u003eK \u003c/i\u003e\u003c/b\u003eseparated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case. \u003c/p\u003e\n\u003cp\u003e\u003cb\u003eSample Input\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\n3\u003cbr\u003e\naaa\u003cbr\u003e\n12\u003cbr\u003e\naabaabaabaab\u003cbr\u003e\n0\u003cbr\u003e\n\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eSample Output\u003c/b\u003e\u003c/p\u003e\nTest case #1\u003cbr\u003e\n2 2\u003cbr\u003e\n3 3\u003cbr\u003e\n\u003cbr\u003e\nTest case #2\u003cbr\u003e\n2 2\u003cbr\u003e\n6 2\u003cbr\u003e\n9 3\u003cbr\u003e\n12 4\u003cbr\u003e\n\u003cp\u003e\u003c/p\u003e\n\u003c/font\u003e\u003c/font\u003e"}}]}