{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003e\nA string is called beautiful if it has the form \u003cb\u003eAA\u003csup\u003er\u003c/sup\u003eAA\u003csup\u003er\u003c/sup\u003e\u003c/b\u003e where \u003cb\u003eA\u003c/b\u003e is some non-empty string and \u003cb\u003eA\u003csup\u003er\u003c/sup\u003e\u003c/b\u003e is the reversed \u003cb\u003eA\u003c/b\u003e.\nYou are given a string \u003cb\u003eS\u003c/b\u003e composed only of lowercase letters of the English alphabet. Find the number of its beautiful substrings. Equal substrings in different positions are considered different. For example, the string \u003cb\u003eaaaaa\u003c/b\u003e has \u003cb\u003e2\u003c/b\u003e different substrings because we have beautiful substring \u003cb\u003eaaaa\u003c/b\u003e in two different positions.\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003e The first line contains a single integer \u003cb\u003eT \u003c\u003d 10\u003c/b\u003e, the number of test cases. \u003cb\u003eT\u003c/b\u003e test cases follow. The only line of each test case contains a non-empty string composed only of lowercase letters of the English alphabet. The length of the string is not greater than \u003cb\u003e100000\u003c/b\u003e.\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003e For each test case, output a single line containing the number of beautiful substrings of the corresponding string.\n\n\u003ch3\u003eExample\u003c/h3\u003e\n\n\u003cpre\u003e\n\u003cb\u003eInput:\u003c/b\u003e\n6\naaaa\naaaaa\nabbaabba\nabbaabb\nabaaba\nxxyyxxxxyyxx\n\n\u003cb\u003eOutput:\u003c/b\u003e\n1\n2\n1\n0\n0\n2\n\u003c/pre\u003e\n"}}]}