{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eBạn có một chuỗi \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e \u003d \u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e... \u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e|\u003ci\u003es\u003c/i\u003e|\u003c/sub\u003e\u003c/span\u003e có độ dài \u003cspan class\u003d\"tex-span\"\u003e|\u003ci\u003es\u003c/i\u003e|\u003c/span\u003e, bao gồm các chữ cái tiếng Anh thường. Cũng có \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e truy vấn, mỗi truy vấn được mô tả bởi hai số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ |\u003ci\u003es\u003c/i\u003e|)\u003c/span\u003e. Câu trả lời cho truy vấn là số lượng chuỗi con của chuỗi \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e[\u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e... \u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e]\u003c/span\u003e, mà là chuỗi đối xứng.\u003c/p\u003e\u003cp\u003eChuỗi \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e[\u003ci\u003el\u003c/i\u003e... \u003ci\u003er\u003c/i\u003e] \u003d \u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003el\u003c/i\u003e\u003c/sub\u003e\u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003el\u003c/i\u003e + 1\u003c/sub\u003e... \u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003er\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003el\u003c/i\u003e ≤ \u003ci\u003er\u003c/i\u003e ≤ |\u003ci\u003es\u003c/i\u003e|)\u003c/span\u003e là một \u003cspan class\u003d\"tex-font-style-it\"\u003echuỗi con\u003c/span\u003e của chuỗi \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e \u003d \u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e... \u003ci\u003es\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e|\u003ci\u003es\u003c/i\u003e|\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eChuỗi \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e được gọi là một \u003cspan class\u003d\"tex-font-style-it\"\u003echuỗi đối xứng\u003c/span\u003e, nếu nó đọc từ trái sang phải và từ phải sang trái là giống nhau. Cụ thể, nếu \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e \u003d \u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e... \u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e|\u003ci\u003et\u003c/i\u003e|\u003c/sub\u003e \u003d \u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e|\u003ci\u003et\u003c/i\u003e|\u003c/sub\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e|\u003ci\u003et\u003c/i\u003e| - 1\u003c/sub\u003e... \u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa chuỗi \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ |\u003ci\u003es\u003c/i\u003e| ≤ 5000)\u003c/span\u003e. Dòng thứ hai chứa một số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003eq\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e)\u003c/span\u003e — số lượng truy vấn. Tiếp theo \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e dòng chứa các truy vấn. Dòng thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e của chúng chứa hai số nguyên cách nhau bởi dấu cách \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ |\u003ci\u003es\u003c/i\u003e|)\u003c/span\u003e — mô tả của truy vấn thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eĐảm bảo rằng chuỗi cho trước chỉ bao gồm các chữ cái tiếng Anh thường.\u003c/p\u003e"}},{"title":"Xuất","value":{"format":"HTML","content":"\u003cp\u003eIn ra \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e số nguyên — các câu trả lời cho các truy vấn. In các câu trả lời theo thứ tự, mà các truy vấn được cho trong đầu vào. Phân tách các số in ra bằng khoảng trắng.\u003c/p\u003e"}},{"title":"Ví dụ 1","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\u003ecaaaba\n5\n1 1\n1 4\n2 3\n4 6\n4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n7\n3\n4\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ghi chú","value":{"format":"HTML","content":"\u003cp\u003eXem xét truy vấn thứ tư trong test case đầu tiên. Chuỗi \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e[4... 6]\u003c/span\u003e \u003d «\u003cspan class\u003d\"tex-font-style-tt\"\u003eaba\u003c/span\u003e». Chuỗi con đối xứng của nó là: «\u003cspan class\u003d\"tex-font-style-tt\"\u003ea\u003c/span\u003e», «\u003cspan class\u003d\"tex-font-style-tt\"\u003eb\u003c/span\u003e», «\u003cspan class\u003d\"tex-font-style-tt\"\u003ea\u003c/span\u003e», «\u003cspan class\u003d\"tex-font-style-tt\"\u003eaba\u003c/span\u003e».\u003c/p\u003e"}}]}