给定一个由小写拉丁字母组成的字符串 $$$s$$$。
您可以对字符串 $$$s$$$ 执行以下操作:选择 $$$s$$$ 的连续子字符串(可能为空)并将其打乱(根据需要对子字符串中的字符重新排序)。
回想一下,回文是一个字符串,从第一个字符到最后一个字符以及从最后一个字符到第一个字符的读取方式相同。例如,字符串 a, 宝贝, ACCA, bcabcbacb 是回文,但是字符串 ab, 阿巴, ccb 不是。
您的任务是确定必须执行上述操作的子字符串的最小可能长度,以便将给定字符串 $$$s$$$ 转换为回文。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个字符串 $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^5$$$),由小写拉丁字母组成。
输入的附加限制:
- 字符串 $$$s$$$ 的长度为偶数;
- 字符串 $$$s$$$ 始终可以转换为回文;
- 所有测试用例 $$$s$$$ 的长度总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 必须执行上述操作才能将给定字符串 $$$s$$$ 转换为回文的子字符串的最小可能长度。
示例
输入复制
4babaccddaaacbacddacbca
输出复制
2 0 3 2
注意
在第一个示例中,可以执行如下操作: baba $$$\右箭头$$$ baab.
在第二个示例中,字符串已经是回文,因此我们可以打乱空子字符串。
在第三个示例中,可以执行如下操作: ddaa $$$\右箭头$$$ 添加a.
在第四个示例中,可以执行如下操作: acbacddacbca $$$\右箭头$$$ acbcaddacbca.