# Everything is still a Palindrome

Every string is made up of palindromes. For example, the string papaya can be formed in the following way :

 1 2 3 pap + aya p + apa + y + a p + a + p + a + y + a 

We need at least two palindromes to form papaya = pap + aya. This file contains a string of length 1000. What is the minimum number of palindromes do we need to construct the string?

Here are 4 sample inputs and their corresponding output for clarification.

Sample Input

 1 2 3 4 abc abcb abcba abcbacabcb 

Sample Output

 1 2 3 4 3 2 1 2 

This is a follow-up of this problem.

×