Minimum Palindromic Substrings Partition

You are given a string \( s \) and your task is to partition it into the minimum number of substrings such that each substring is a palindrome. A palindrome is a string that reads the same forwards and backwards. For example, if \( s = \text{'racecar'} \), the string is already a palindrome and the answer is \( 1 \). If \( s = \text{'aabbd'} \), one optimal partition could be \( [\text{'aa'}, \text{'bb'}, \text{'d'}] \), resulting in an answer of \( 3 \).

Your program should handle multiple test cases. Each test case consists of a single line containing a string. The input is terminated by a line that contains only a period (\( . \)). For each input string (except the terminating line), output a single integer representing the minimum number of palindromic substrings into which the string can be partitioned.

inputFormat

The input consists of several lines, each containing a non-empty string \( s \) made up of lowercase letters. The end of the input is indicated by a line containing a single period (\( . \)).

outputFormat

For each test case, output a single line containing one integer — the minimum number of palindromic substrings the input string can be partitioned into.

racecar
aabbd
abc
madamimadam
.

1
3
3
1