{"code":"sieudoixung","name":"Tiền tố và đối xứng","description":"Cho một xâu $S$ chỉ bao gồm các ký tự số và chữ cái Latin. Gọi $A(S)$ là \"**mức độ xinh đẹp**\" của xâu $S$, và nó được định nghĩa theo công thức truy hồi như sau:\r\n\r\n- $A(S)=0$ nếu $S$ là xâu không đối xứng hoặc là xâu rỗng\r\n\r\n- Gọi $n$ là độ dài của xâu $S$, khi đó ta có: $A(S)=k$ nếu tiền tố và hậu tố có độ dài là $\\left \\lfloor{\\frac{n}{2}}\\right \\rfloor$ của $S$ đều có \"**mức độ xinh đẹp**\" là $k-1$\r\n\r\n**Yêu cầu:**\r\n\r\n- Cho xâu $S$, hãy in ra tổng \"**mức độ xinh đẹp**\" của tất cả các tiền tố của xâu $S$\r\n  \r\n<h4>Input</h4>\r\n\r\n- Dòng thứ nhất chứa số $t(1\\le t\\le 50)$ - Thể hiện số lượng testcase \r\n\r\n- $t$ dòng tiếp theo, mỗi dòng chứa $t$ xâu $S(0\\le |S|\\le 10^5)$\r\n\r\n<h4>Output</h4>\r\n\r\n- Ứng với mỗi testcase, in ra đáp án cần tìm.\r\n\r\n<h4>Example</h4>\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        4\r\n        Qc93vcc11z\r\n        cSschccV2cccqZ\r\n        wccnq1c5gcqEK7mxc7cc\r\n        cccrc6cLCE\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        1\r\n        1\r\n        1\r\n        5\r\n        ```\r\n\r\n!!! question \"Test 2\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        5\r\n        tccPcq2Acc7mcs\r\n        7czY5SG8cGMccvQSQFnc\r\n        cccczsb1kgcySZcccicc\r\n        bDFckccfcrc\r\n        cccuHHcccccGcc\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        1\r\n        1\r\n        8\r\n        6\r\n        6\r\n        ```\r\n\r\n!!! question \"Test 3\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        2\r\n        abac\r\n        aa\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        3\r\n        3\r\n        ```\r\n    \r\n    ??? warning \"Note\"\r\n        - Xét testcase $3$:\r\n\r\n        + Đối với xâu $\"abac\"$, ta sẽ có các tiền tố sau: $\"a\",\"ab\",\"aba\",\"abac\"$. và \"**mức độ xinh đẹp**\" của chúng tương ứng là: $A(\"a\")=1,A(\"ab\")=0,A(\"aba\")=2,A(\"abac\")=0$. Do đó tổng \"**mức độ xinh đẹp**\" của xâu đã cho là: $1+0+2+0=3$","points":450.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}