CF2069D.Palindrome Shuffle

给定一个由小写拉丁字母组成的字符串 $s$。

你可以对字符串 $s$ 执行以下操作：选择一个连续的（可能为空的）子串，并对其进行洗牌（即重新排列子串中的字符顺序）。

注意：回文是指正向和反向读取相同的字符串。例如，字符串 a、bab、acca、bcabcbacb 是回文，而 ab、abbbaa、cccb 则不是。

你的任务是确定为了将给定字符串 $s$ 转换为回文，必须进行操作的最小子串长度。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例仅包含一行字符串 $s$（$2 \le |s| \le 2 \cdot 10^5$），由小写拉丁字母组成。

输入额外约束：

• 字符串 $s$ 的长度为偶数；
• 字符串 $s$ 总能被转换为回文；
• 所有测试用例的 $s$ 长度总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数——为了将字符串转换为回文必须进行操作的最小子串长度。

第一个示例中，可以按如下方式操作：baba → baab。

第二个示例中，字符串已经是回文，因此可以选择空子串进行操作。

第三个示例中，可以按如下方式操作：ddaa → adda。

第四个示例中，可以按如下方式操作：acbacddacbca → acbcaddacbca。

翻译由 DeepSeek R1 完成