Palindrome Encoding

Time limit2sMemory limit128 MB

Summary

Given a binary string, repeatedly delete the second half of any even-length palindromic substring and find the minimum length achievable.

Level: Hard8 of 10
Topics: Dynamic programming, String, String matching, Recursion
Solved: No attempts yet

Problem

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.

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.
Delete the second half of the chosen substring. For example, if 0110 is chosen, its second half 10 is deleted and only 01 remains.
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.

Input

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

1 <= |S| < 50

Output

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

Hint

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.

Examples3

Example 1
Input
```
0111001
```
Expected output
```
2
```
Example 2
Input
```
0
```
Expected output
```
1
```

Example 3

Input

01010111100110101110000001011000101000010111000111

Expected output