Problem Description

给定一个长度为 $n$ 的字符串 $S$。现在有一个字符串 $T$，初始时 $T=S$（在接下来的操作中 $S$ 不变）.

定义对 $T$ 的删除操作：每次操作删除 $T$ 开头或结尾**恰好一个字符**，同时花费『（操作前）$T$ 在 $S$ 中的出现次数』的代价。

现在希望通过 $n$ 次操作将 $T$ 变为空串，求最小的总花费

Input

第一行一个整数 $ T (1 \leq T \leq 5 \times 10^4)$ 表示测试用例数量。

对每个测试用例，输入一个**仅包含小写字母**的字符串 $ S (1 \leq \sum |S| \leq 10^6) $.

Output

对每个测试用例，输出一行一个整数，表示最小总花费。

5
abc
aaba
aaabb
legendy
ygfuygfu

3
4
6
7
9

Hint

例如对于 $S=T=aaabb$，一种可能的操作方式如下：$\underline{a}aabb \xrightarrow{1} \underline{a}abb \xrightarrow{1} \underline{a}bb\xrightarrow{1}\underline{b}b\xrightarrow{1}\underline{b}\xrightarrow{2}\epsilon$.

（$\epsilon$ 表示空串，$\to$ 上的数字表示花费）