Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3296
Connecting the Segments

Time Limit: 1 Second      Memory Limit: 131072 KB

Aaron's mm's birthday is coming soon, in order to give her a surprise, he decide to make a beautiful necklace for her. the necklace consists of many beautiful beads. And it should be considered as a string rather than a circle, so "abc" and "cab" are considered as two different necklaces.

Aaron has a strange machine that can produce any palindromic segment of beads. If the necklace is a palindrome, this machine is the only thing needed; otherwise, Aaron has to use the machine to produce several palindromic segments first, then use a special tool to connect them and form the whole necklace.

The special tool can be used to connect two segments into one segment. The original two segments can be overlapped with each other, if the overlapping parts are identical. For example, after using this special tool segment "aba" and segment "aca" can be connected into "abaaca" or "abaca".

Now given the necklace, please help Aaron to calculate the minimal times this special tool should be used in order to make the necklace. Note that you can use the strange machine to produce all kinds of palindromic segments as many times as possible.


Input consists of multiple test cases (about 10 cases)!

For each case there's a line contain a string which describes the necklace, the color of each beads of the necklace is represented by a lowercase letter, the length of the string is no more than 50000.


Output the minial times the special tool should be used.

Sample Input


Sample Output


Author: ZHOU, Yilun
Source: ZOJ Monthly, February 2010
Submit    Status