Magical Forest Clearing

You are given a magical forest represented as a string consisting solely of the characters x and y. Each character represents a type of tree. A spell can clear one tree of a particular type. In order to clear the entire forest, you can only cast spells on the minority tree type. Formally, if the forest contains n_x trees of type x and n_y trees of type y, then the minimal number of spells required is:

[ \min(n_x, n_y) ]

You are given t test cases. For each test case, determine the minimal number of spells required to clear the given forest.

Example:

Input:
2
xxyxy
yyxx
Output:
2
2

</p>

In the first test case, the forest "xxyxy" has 3 occurrences of x and 2 occurrences of y, so the answer is min(3,2) = 2.

inputFormat

The input begins with an integer t (1 ≤ t ≤ 10⁵) on the first line, denoting the number of test cases. Each of the following t lines contains a non-empty string representing the forest. Each string consists only of the characters x and y.

Input is provided via standard input (stdin).

outputFormat

For each test case, output the minimal number of spells required to clear the forest, each on its own line. The output should be written to standard output (stdout).

## sample

1
xy

1