字符串 $$$a=a_1a_2\dots a_n$$$ 被调用,即使它由长度为 $$$2$$$ 且由相同字符组成的字符串串联(连接)组成。换句话说,即使同时满足两个条件,字符串 $$$a$$$ 也是偶数:
- 它的长度 $$$n$$$ 是偶数;
- 对于所有奇数 $$$i$$$ ($$$1 \le i \le n - 1$$$),满足 $$$a_i = a_{i+1}$$$ 。
例如,以下字符串是偶数:“”(空字符串)、“tt”、“aabb”、“oooo”和“ttrrrroouuuuuuuukk”。以下字符串不是偶数:“aaa”、“abab”和“abba”。
给定一个由小写拉丁字母组成的字符串 $$$s$$$。找出要从字符串 $$$s$$$ 中删除的最少字符数,以使其均匀。删除的字符不必是连续的。
输入
输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) – 测试中的测试用例数量。
测试用例的描述如下。
每个测试用例由一个字符串 $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$) 组成,其中 $$$|s|$$$ — 字符串 $$$s$$$ 的长度。该字符串由小写拉丁字母组成。
保证所有测试用例的 $$$|s|$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个数字 - 必须删除以使 $$$s$$$ 偶数的最小字符数。
示例
输入 #1
6 aabbdabdccc zyx aaababbb aabbcc oaoaaaoo bmefbmuyw
输出 #1
3 3 2 0 2 7
注意
在第一个测试用例中,您可以删除索引为 $$$6$$$、$$$7$$$ 和 $$$9$$$ 的字符以获得偶数字符串“aabbddcc”。
在第二个测试用例中,每个字符只出现一次,因此为了获得偶数字符串,必须从字符串中删除所有字符。
在第三个测试用例中,您可以通过删除例如第 $$$4$$$ 和第 $$$6$$$ 字符来获得偶数字符串“aaaabb”,或者通过删除第 $$$5$$$ 字符和前三个字符中的任何一个来获得字符串“aabbbb”。