Given a string s of length n, design an algorithm that outputs the smallest number k such that s = w1w2 . . . wk where each wi is a palindrome. In other words, find the smallest k such that s can be written as a concatenation of k palindromes. For the definition of a palindrome see practice problems. For example if s = "add" then the algorithm should output k = 2 since we can take w1 ="a" and w2 ="dd". On the other hand, if s = "ada", then the algorithm should output k = 1.