Maximum Palindromic Strings Rearrangement

Given a string ( s ), determine the maximum number of palindromic strings that can be constructed by rearranging its characters. You are allowed to reorder the letters arbitrarily and then partition the string into several palindromic substrings. The idea is based on character frequencies. Let ( odd_count ) be the number of characters that appear an odd number of times. Then the maximum number of palindromic strings that can be formed is given by:

[ \text{result} = \frac{|s| - odd_count}{2} + \begin{cases} 1 & \text{if } odd_count > 0\ 0 & \text{otherwise} \end{cases} ]

Each test case contains a single string and your task is to output the computed result on a new line.

inputFormat

The first line contains an integer ( T ) representing the number of test cases. Each of the following ( T ) lines contains a non-empty string consisting of lowercase English letters.

outputFormat

For each test case, output a single integer on a new line representing the maximum number of palindromic strings that can be formed from the given string.## sample

3
aabb
abc
aaaaaa

2
1
3