Given a string consisting only of digits. In one move you can delete from this any sequence of consecutive identical digits. What is the minimum number of moves in which you can delete the entire row?

Input

One string of digits. The string length does not exceed 300 characters.

Output

Print the minimum number of moves in which you can delete the entire line.