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

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

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

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

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

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

例如对于 $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$

（$ϵ$ 表示空串，$→$ 上的数字表示花费）