Palindroms ir burtu virkne, kas vienādi lasāma gan no kreisās puses uz labo, gan no labās puses uz kreiso. Piemēram, palindromi ir virknes 'ala', 'sileputrakartupelis','f', bet nav 'ligzda','alas' un 'kuku'.

Ja burtu virkne nav palindroms, to vienmēr var "sagriezt" daļās, no kurām katra ir palindroms.

Uzrakstiet programmu, kas dotai burtu virknei noskaidro mazāko skaitu fragmentu, kādā tā jāsagriež, lai katra daļa būtu palindroms!

Ievaddatu vienīgajā rindā dota burtu virkne - ne vairāk kā 100 angļu alfabēta mazie burti (a-z).

Izvaddatu vienīgajā rindā jāizvada naturāls skaitlis - mazākais iespējamais fragmentu skaits, kādā jāsadala dotā virkne.

Uzdevums izmantots Horvātijas informātikas olimpiādē 2001.gadā