P14021 [ICPC 2024 Nanjing R] Border Jump 2

由于评测机性能差异，本题时限相较原题提升了 1 秒。

You are given a string $S$ consisting of lower-cased English letters. You need to perform some operations on $S$ until it becomes empty. Each time you can perform one of the following three operations: - Delete the first character of $S$. - Delete the last character of $S$. - Choose a good substring $S'$ of $S$ and replace $S$ with $S'$. A non-empty string $S'$ is called a good substring of string $S$ if and only if $S'\neq S$, $S'$ is a prefix of $S$, and the reverse of $S'$ is a suffix of $S$. The reverse of a string $p_1p_2\cdots p_k$ of length $k$ is another string $p_kp_{k-1}\cdots p_1$ of length $k$. What's the maximum number of type $3$ operations can you perform?

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first and only line contains a string $S$ ($1\le |S|\le 10^5$) consisting of lower-cased English letters. It is guaranteed that the sum of $|S|$ over all test cases does not exceed $2\times 10^5$.

For each test case, output one line containing one integer indicating the maximum number of type $3$ operations you can perform.

For the first sample test case: $\texttt{aaaa} \xrightarrow{\text{op. 3}} \texttt{aaa} \xrightarrow{\text{op. 3}} \texttt{aa} \xrightarrow{\text{op. 3}} \texttt{a} \xrightarrow{\text{op. 2}} \varnothing$. For the second sample test case: $\texttt{abbaabba} \xrightarrow{\text{op. 3}} \texttt{abbaabb} \xrightarrow{\text{op. 1}} \texttt{bbaabb} \xrightarrow{\text{op. 3}} \texttt{bbaab} \xrightarrow{\text{op. 1}} \texttt{baab} \xrightarrow{\text{op. 3}} \texttt{baa} \xrightarrow{\text{op. 1}} \texttt{aa} \xrightarrow{\text{op. 3}} \texttt{a} \xrightarrow{\text{op. 1}} \varnothing$.