题目描述

小 L 提出了一个问题：

给定一个长度为 $n$ 的字符串 $S$，只包含小写字母。

你需要选择 $S$ 的若干非空子串，使得它们两两不相交，并且每个子串都是回文串。

假设你选择了满足上述条件的 $K$ 个子串 $(s_1, s_2 \dots s_k)$，你的得分是所有子串的长度之和减去 $K$。即 $\sum_{i = 1}^{K} len(s_i) - K$。

但小 L 是个专注的人，为了增加难度，小 L 要求每个回文串最多只包含一种字母。

小 L 希望你能求出最大得分。

输入格式

第一行一个正整数 $T$，表示测试组数。

对于每组测试数据：只有一行，包含一个长度为 $n$ 的字符串，只包含小写字母。

$T \leq 20$，$\sum n \leq 10^{6}$。

输出格式

对于每组测试数据，输出一个数，表示最大得分。

2
etxabaxtezwkdwokdbbb
aaaaa

2
4