Minimum Removals for Palindrome Permutation

Given a string s consisting of lowercase letters, determine the minimum number of characters that must be removed so that the remaining characters can be rearranged to form a palindrome.

A string can be rearranged into a palindrome if at most one character has an odd frequency. In other words, if the number of characters that appear an odd number of times is \(k\), then the minimum number of removals is \(\max(0, k-1)\).

For example, for the string "abcde", each character appears once (i.e. \(k=5\)), so you must remove 4 characters to allow the remaining characters to form a palindrome permutation.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases.

Each of the following \(T\) lines contains a single string s consisting of lowercase English letters.

outputFormat

For each test case, print one line containing the minimum number of characters that must be removed so that the remaining characters can be rearranged into a palindrome.

## sample

3
abcde
aabbcc
abccba

4
0
0

</p>