题目描述

如果一个字符串 $a = a_1 a_2 \ldots a_n$ 可以看成是由一对一对长度为 $2$ 且包含相同字符的字符串拼接而成的，则我们称该字符串为一个”偶数串”。

换句话说，如果字符串 $a$ 同时满足如下两个性质，则我们称字符串 $a$ 是偶数串：

• 字符串 $a$ 的长度 $n$ 是偶数；
• 对于任意 奇数 下标 $i(1 \le i \le n-1)$，均有 $a_i = a_{i+1}$（即：$a_1 = a_2, a_3 = a_4, \ldots, a_{n-1} = a_n$）。

比如：

• 字符串 "" (空串), "tt", "aabb", "oooo", and "ttrrrroouuuuuuuukk" 都是偶数串；
• 字符串 "aaa", "abab" and "abba" 都不是偶数串。

给定一个一个字符串 $s$，你可以对删除这个字符串中的一些字符，要求剩余没有被删除的字符串在不改变先后顺序的情况下组成的字符串是一个偶数串。问：最少需要删除几个字符？

输入格式

输入包含多组测试数据。

输入的第一行包含一个整数 $t(1 \le t \le 100)$，表示测试数据组数。

接下来每一行包含一组测试数据，是一个仅由小写英文字母组成的字符串 $s$（$s$ 的长度不超过 $2 \cdot 10^5$）。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示将 $s$ 变成偶数串至少需要删除几个字符。

6
aabbdabdccc
zyx
aaababbb
aabbcc
oaoaaaoo
bmefbmuyw

3
3
2
0
2
7

说明/提示

样例解释

第 $1$ 组测试数据中，可以删除第 $6,7,9$ 个字符，得到偶数串 "aabbddcc"。

第 $2$ 组测试数据中，需要将所有字符都删掉才能得到偶数串（一个空串）。

第 $3$ 组测试数据中，可以删掉第 $4$ 和 $6$ 个字符得到偶数串 "aaaabb"，或者删掉第 $5$ 个字符以及前三个字符中的任意一个得到偶数串 "aabbbb"。

数据规模与约定

设 $|s|$ 表示字符串 $s$ 的长度，则：

• 对于 $20\%$ 的数据，$t = 1, |s| \le 20$
• 对于 $50\%$ 的数据，$t \le 10, |s| \le 2000$
• 对于 $100\%$ 的数据，$t \le 100, 1 \le |s| \le 2 \cdot 10^5$，且所有测试数据的 $n$ 之和不超过 $2 \cdot 10^5$