Palindrome Encoding

Jungyu made an encoding rule that shortens binary strings.

The rule applies only to strings made of 0 and 1. One operation works as follows.

1. Choose one contiguous substring of the current string that has even length and is a palindrome. A palindrome reads the same from left to right and from right to left.
2. Delete the second half of the chosen substring. For example, if 0110 is chosen, its second half 10 is deleted and only 01 remains.
3. Operations may be repeated in any order until no even-length palindromic substring can be chosen.

Given a string S, find the shortest possible length among all strings that can result from this encoding.

The first line contains a string S made only of 0 and 1.

• 1 <= |S| < 50

Print the minimum possible length of a string that can result from the encoding.

In the first visible test, choosing the suffix 1001 changes the string to 01110. Then choosing 11 gives 0110, and finally choosing 0110 leaves 01, whose length is 2.