Description

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?

Input Format

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$.

Output Format

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

3
aaaa
abbaabba
xy

3
4
0

Hint

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$.