In Pragyan, every shop has their own discount methods to attract the customers. One discount method called Buy 1 Get 1 caught your friend's attention. That is, if your friend buys one object, then your friend can get one additional object with the same color without charge by Buy 1 Get 1. Your friend lists the needed objects as a string S, each letter denotes one object, and the same letters denote the same object, and the different letters denote the different objects. The cost of each object is 1. Your task is to calculate the minimum cost for getting all the objects your friend is asking for. Help Him !!!

Input

The first line of input contains a single line T, which represents the number of test cases. Then T lines will follow, and each contains a string S, which represents the objects your friend needs.

Output

Output the minimum cost for each test case.

Constraints

1 ≤ T ≤ 100 1 ≤ |S| ≤ 200, where |S| represents the length of the string S. The string S is case sensitive, and will contain only English characters in the range [a-z], [A-Z].