Maximum Distinct Characters After Adjacent Removal

You are given a string \(S\). You must repeatedly remove adjacent pairs of equal characters from the string. After you have performed as many operations as possible, determine the maximum number of distinct characters that remain in the resultant string.

For example, consider \(S = \texttt{abbaca}\):

1. Remove the adjacent \(bb\) to get \(aaca\).
2. Remove the adjacent \(aa\) to get \(ca\).

The remaining distinct characters are \(\{c, a\}\), so the answer is 2.

Note: If the string becomes empty, the number of distinct characters is 0.

inputFormat

The input is given from standard input and consists of multiple test cases. The first line contains a single integer \(T\), the number of test cases. Then \(T\) lines follow, each containing a non-empty string \(S\) composed of lowercase letters.

Input Example:

2
abbaca
aabbcc

outputFormat

For each test case, output the maximum number of distinct characters remaining after repeatedly removing adjacent duplicate characters. Each answer should be printed on a separate line.

Output Example:

2
0

## sample

2
abbaca
aabbcc

2
0

</p>