A14867 | 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.

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$ .

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