{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e爱丽丝想要给鲍勃发送一条机密消息。她尝试用自己原创的加密方法对消息进行加密。消息是一个字符串$S$,由$N$个小写字母组成。\u003cbr\u003e\u003cbr/\u003e$S[a…b]$表示S的一个子字符串,范围从$S[a]$到$S[b]$($0≤a≤b\u0026lt;N$)。如果前$i$个字母已经被加密,爱丽丝将尝试找到一个神奇的字符串$P$。假设$P$有$K$个字母,$P$是满足$P\u003dS[T...T+K-1]$($0≤T\u0026lt;i$,$T+K≤N$)和$P\u003dS[i…i+K-1] (i+K≤N)$的最长字符串。换句话说,$P$是$S$的一个子字符串,其起始地址在$[0...i-1]$内,并且$P$也是$S[i...N-1]$的前缀。如果$P$存在,爱丽丝将在密文中附加整数$K$和$T$。如果$T$不唯一,爱丽丝将选择最小的一个。然后$i$增加$K$。如果$P$不存在,爱丽丝将在密文中附加-1和字母$S[i]$的ASCII码,然后增加$i$1。\u003cbr\u003e\u003cbr/\u003e显然,第一个字母不能被加密。也就是说,当$i\u003d0$时,$P$不存在。因此,密文的第一个整数必须为-1,第二个整数是$S[0]$的ASCII码。\u003cbr\u003e\u003cbr/\u003e当$i\u003dN$时,所有字母都被加密,爱丽丝得到最终的密文,其中包含许多整数对。请帮助爱丽丝实现这个方法。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入的第一行包含一个整数$T$,表示测试用例的数量($T≤50$)。每个测试用例包含一个字符串行,该行不超过100000个小写字母。保证字符串的总长度不超过$2×10^6$。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,首先输出一行“\u003cb\u003eCase #X:\u003c/b\u003e”。$X$是从1开始的测试用例编号。在接下来的行中输出密文。每行包含两个用单个空格分隔的整数。"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\naaaaaa\r\naaaaabbbbbaaabbc\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1:\r\n-1 97\r\n5 0\r\nCase #2:\r\n-1 97\r\n4 0\r\n-1 98\r\n4 5\r\n5 2\r\n-1 99\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}