{"trustable":false,"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":"MD","content":"lyd实在是太有名了,我们称一个串s为丁哥串当且仅当s的字典序小于s任意循环移位的字典序,如今每次查询,输入两个串a,b,请你输出ab子串中最长的丁哥串的长度。"}},{"title":"Input","value":{"format":"MD","content":"有多组测试数据\n第一行一个整数 T代表测试组数\n接下来一行2个数n,m,代表总的串数,查询次数\n接下来n行每行一个串\n接下来m行每行两个数i,j,查询ij串 1\u003c\u003di,j\u003c\u003dn\nn\u003c\u003dm\u003c\u003d1e5\n单个串长度不超过1e5,串的总长度不超过5e6."}},{"title":"Output","value":{"format":"MD","content":"每行输出每次查询的结果"}},{"title":"Sample Input","value":{"format":"MD","content":"1\n2 1\naa\nbb\n1 2"}},{"title":"Sample Output","value":{"format":"MD","content":"4"}}]}