Sau một thời gian phấn đấu và tích cực ôn luyện trong đội tuyển, hai bạn Tí và Tèo đã vượt qua kì thi chọn học sinh giỏi cấp trường, chính thức được chọn vào đội tuyển học sinh giỏi môn Tin học của trường XYZ tham dự kì thi chọn học sinh giỏi cấp tỉnh. Lần này, hai bạn được thầy dạy rất nhiều chuyên đề chuyên sâu trong lập trình. Khi học đến chuyên đề về xâu kí tự, Tí biết rằng xâu đối xứng (palindrome) là xâu nếu như khi đọc xâu này từ trái sang phải hay từ phải sang trái thì xâu đó không thay đổi.

Ví dụ: Các xâu: "ioi", "madam", "abba" là các xâu đối xứng, còn các xâu: "voi", "abab", "tiok" không phải là các xâu đối xứng.

Tí nhận thấy rằng, nếu như coi xâu chỉ gồm một kí tự cũng là một palindrome thì một xâu kí tự bất kì có thể biểu diễn như một dãy các palindrome.

Ví dụ: Xâu "banana" có thể biểu diễn dưới dạng dãy các palindrome theo nhiều cách, chẳng hạn:

• "banana" = "b" + "anna"
• "banana" = "b" + "ana" + "n" + "a"
• "banana" = "b" + "a" + "nan" + "a"
• ...

Tí liền hỏi bạn Tèo: Nếu cho xâu kí tự $S$ chỉ gồm các kí tự chữ cái in thường thì trong cách biểu diễn dưới dạng dãy các palindrome, cách nào thu được số lượng palindrome ít nhất.

Yêu cầu: Hãy lập trình giúp Tí và Tèo tìm ra cách biễu diễn xâu $S$ dưới dạng một dãy gồm ít nhất các palindrome.

banana

2

bobseesanna

3