题目描述

您有一个由小写英文字母组成的字符串 $S$。您需要对 $S$ 执行若干次操作，直到它变为空字符串。每次您可以执行以下三种操作中的一种：

• 删除 $S$ 的第一个字符。
• 删除 $S$ 的最后一个字符。
• 选择 $S$ 的一个好子串 $S'$，并将 $S$ 替换为 $S'$。

一个非空字符串 $S'$ 被称为 $S$ 的好子串，当且仅当 $S'\neq S$，$S'$ 是 $S$ 的前缀，且 $S'$ 的反串是 $S$ 的后缀。长度为 $k$ 的字符串 $p_1p_2\cdots p_k$ 的反串是另一个长度为 $k$ 的字符串 $p_kp_{k-1}\cdots p_1$。

求最多能执行多少次第 $3$ 种操作。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个由小写字母组成的字符串 $S$（$1\le |S|\le 10^5$）。

保证所有测试数据 $|S|$ 之和不超过 $2\times 10^5$。

输出格式

每组测试数据输出一行一个整数，表示最多能执行多少次第 $3$ 种操作。

3
aaaa
abbaabba
xy

3
4
0

提示

对于第一组样例数据：$\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$。

对于第二组样例数据：$\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$。