Minimum Palindrome Partitioning Cuts

Given a string \(s\), partition it such that every substring is a palindrome. A palindrome is a string that reads the same forwards and backwards. Your task is to compute the minimum number of cuts needed to partition the string so that every part is a palindrome.

For example, for the string abcbm, the optimal partition is a | bcb | m, which requires 2 cuts. If the entire string is already a palindrome, then no cuts are required.

You may make use of the following criterion: a substring \(s[i:j]\) is a palindrome if

[ s[i] = s[j] \quad \text{for all } i, j \text{ in the substring} ]

inputFormat

The input consists of multiple lines. Each line contains a single non-empty string \(s\) representing a test case. The input terminates with a line containing only END. Do not process the termination line.

outputFormat

For each test case, output a single line containing one integer: the minimum number of cuts needed to partition the string so that every partition is a palindrome.

## sample

abcbm
END

2

</p>