题目描述

如果一个字符串 $a=a_1a_2…a_n$ 是由长度为 $2$ 的由相同字符组成的字符串连接而成，则称其为偶字符串。换句话说，当两个条件同时满足时，字符串a是偶字符串：

它的长度 $n$ 是偶数； 对于所有的奇数 $i(1≤i≤n−1)$，都有 $a_i=a_i+1$。

例如，以下字符串是偶字符串： 、tt、aabb、oooo 和 ttrrrroouuuuuuuukk。以下字符串不是偶字符串：aaa、abab 和 abba。

给定一个由小写拉丁字母组成的字符串 $s$，找出从字符串 $s$ 中删除字符所需的最小数量，以使其成为偶字符串。被删除的字符不必连续。

输入格式

输入数据的第一行包含一个整数 $t(1≤t≤10^4)$ ——测试中测试用例的数量。

接下来是每个测试用例的描述。

每个测试用例包括一个字符串 $s(1≤|s|≤2⋅10^5)$，其中 $|s|$ 是字符串 $s$ 的长度。该字符串由小写拉丁字母组成。

保证所有测试用例中 $|s|$ 的总和不超过 $2⋅10^5$。

输出格式

对于每个测试用例，请输出一个数字——必须删除的字符的最小数量，以使 $s$ 成为偶字符串。

测试样例

6
aabbdabdccc
zyx
aaababbb
aabbcc
oaoaaaoo
bmefbmuyw

3
3
2
0
2
7

样例说明

在第一个测试用例中，您可以删除索引为 $6$、$7$ 和 $9$ 的字符，以获得一个偶字符串 aabbddcc。

在第二个测试用例中，每个字符都恰好出现一次，因此为了得到一个偶字符串，必须从字符串中删除所有字符。

在第三个测试用例中，您可以通过删除例如第 $4$ 个和第 $6$ 个字符来获得偶字符串 aaaabb，或者通过删除第 $5$ 个字符和前三个字符中的任意一个来获得字符串 aabbbb。