URI Online Judge | 2588

Game of Palindromes

By Ricardo Martins, IFSULDEMINAS BR Brazil

Timelimit: 1

Rener was a boy who loved palindromes. So much that he invented a game with these. Given a sequence of letters, how many more would have to be added, at least so that some permutation of this sequence formed a palindrome. For example, potatoes need to add a b at the end to flip the palate. In another example, aabb, you do not need to add any letter because you do the abba or baab palindrome. In another example, abc needs two more letters, to form a palindrome, which can be abcba, acbca, bacab, bcacb, cabac, or cbabc.

Write a program that, given a sequence of letters, tells you the minimum number of letters that need to be added to the sequence, so that there is at least one anagram that forms a palindrome.

Input

There will be several test cases. In each case, a sequence of up to 1000 letters is shown. Test cases end with end of file.

Output

For each test case, print an integer value, corresponding to the minimum number of letters to be added so that the sequence becomes a palindrome in one of its permutations.

Input Sample Output Sample

batata
aabb
abc

1
0
2