human
PYTHON3 solution for "This is a simplified version of the problem B2. Perhaps you should read the problem B2 before you start solving B1.

Paul and Mary have a favorite string s which consists of lowercase letters of the Latin alphabet. They want to paint it using pieces of chalk of two colors: red and green. Let's call a coloring of a string wonderful if the following conditions are met:

  1. each letter of the string is either painted in exactly one color (red or green) or isn't painted.

  2. each two letters which are painted in the same color are different.

  3. the number of letters painted in red is equal to the number of letters painted in green.

  4. the number of painted letters of this coloring is maximum among all colorings of the string which meet the first three conditions. 


E. g. consider a string s equal to "kzaaa". One of the wonderful colorings of the string is shown in the figure.

 The example of a wonderful coloring of the string "kzaaa".

Paul and Mary want to learn by themselves how to find a wonderful coloring of the string. But they are very young, so they need a hint. Help them find k — the number of red (or green, these numbers are equal) letters in a wonderful coloring.

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of test cases. Then t test cases follow.

Each test case consists of one non-empty string s which consists of lowercase letters of the Latin alphabet. The number of characters in the string doesn't exceed 50.

Output

For each test case, output a separate line containing one non-negative integer k — the number of letters which will be painted in red in a wonderful coloring.

Example

Input

5
kzaaa
codeforces
archive
y
xxxxxx

Output

2
5
3
0
1

Note

The first test case contains the string from the statement. One of the wonderful colorings is shown in the figure. There's no wonderful coloring containing 3 or more red letters because the total number of painted symbols will exceed the string's length.

The string from the second test case can be...":



=====
Give me a Python code to find a wonderful coloring of the string?
assistant
#Here is Python code to find a wonderful coloring of the string.
 def laske(luku: str):
    pass

# codeforces
# archive
# y
# xxxxxx

def main2():
    mjono = 'xxxxxx'
    maarat = {}
    summa = 0

    for merkki in mjono:
        if not merkki in maarat:
            maarat[merkki] = 0
        if maarat[merkki] < 2:
            maarat[merkki] += 1
            summa += 1

    print(summa // 2)

def main():
    t = int(input())
    mjonot = []
    for i in range(1, t+1):
        mjono = input()
        mjonot.append(mjono)

    for mjono in mjonot:
        maarat = {}
        summa = 0
        for merkki in mjono:
            if not merkki in maarat:
                maarat[merkki] = 0
            if maarat[merkki] < 2:
                maarat[merkki] += 1
                summa += 1

        print(summa // 2)

main()