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

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

Sample Input

5
abc
aaba
aaabb
legendy
ygfuygfu

Sample Output

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$ 上的数字表示花费）