CF1660C.Get an Even String

A string $a=a_1a_2\dots a_n$ is called even if it consists of a concatenation (joining) of strings of length $2$ consisting of the same characters. In other words, a string $a$ is even if two conditions are satisfied at the same time:

• its length $n$ is even;
• for all odd $i$ ($1 \le i \le n - 1$), $a_i = a_{i+1}$ is satisfied.

For example, the following strings are even: "" (empty string), "tt", "aabb", "oooo", and "ttrrrroouuuuuuuukk". The following strings are not even: "aaa", "abab" and "abba".

Given a string $s$ consisting of lowercase Latin letters. Find the minimum number of characters to remove from the string $s$ to make it even. The deleted characters do not have to be consecutive.

如果一个字符串 $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$ 变为偶字符串所需删除的最少字符个数。被删除的字符不必连续。

The first line of input data contains an integer $t$ ($1 \le t \le 10^4$) —the number of test cases in the test.

The descriptions of the test cases follow.

Each test case consists of one string $s$ ($1 \le |s| \le 2 \cdot 10^5$), where $|s|$ — the length of the string $s$. The string consists of lowercase Latin letters.

It is guaranteed that the sum of $|s|$ on all test cases does not exceed $2 \cdot 10^5$.

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

随后是各测试用例的描述。

每个测试用例由一个字符串 $s$ 组成（$1 \le |s| \le 2 \cdot 10^5$），其中 $|s|$ 表示字符串 $s$ 的长度。该字符串仅由小写拉丁字母组成。

保证所有测试用例的 $|s|$ 之和不超过 $2 \cdot 10^5$。

For each test case, print a single number — the minimum number of characters that must be removed to make $s$ even.

对于每个测试用例，输出一个整数——使字符串 $s$ 变为偶串所需删除的最少字符数。

In the first test case you can remove the characters with indices $6$, $7$, and $9$ to get an even string "aabbddcc".

In the second test case, each character occurs exactly once, so in order to get an even string, you must remove all characters from the string.

In the third test case, you can get an even string "aaaabb" by removing, for example, $4$-th and $6$-th characters, or a string "aabbbb" by removing the $5$-th character and any of the first three.

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

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

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