Nobita wants vengeance of his bullies. He wants some special gadget that gives him the power to make things fly using his mind.
He requests Doraemon for the gadget. Doraemon gives him a "Telekinesis Helmet". Using this helmet one can control things with his mind.

But, one has to train before using this gadget. So, Doraemon takes Nobita to a training arena in future. 
In the training arena, there are a lot of candles of different colors. Doraemon arranges N candles (can be of different colors) in a line.
Now, Nobita's task is to make the candles fly using the "Telekinesis Helmet" and put them aside.
Nobita did that easily.

Now, Doraemon gives him an even harder task. In this second task, Doraemon again arranges N candles (can be of different colors) in a line and asks Nobita to
make them fly and put aside but this time he added a condition, that now Nobita can only lift the consecutive candles which form a palindrome with their colors. 

Since Nobita is lazy, he wants to know beforehand the minimum number of times he will have to use the Telekinesis Helmet to complete the task.

For example,
If Doraemon arranges 8 candles whose color representations are "rggbcycr", then in the first usage he can fly the candles "cyc". 
Now remaining candles are "rggbr". Now in the second usage, he can fly the candle "b".
Now remaining candles are "rggr". Now he can fly all the candles as "rggr" form a palindrome.
Hence, he will have to use the Telekinesis Helmet 3 times.

INPUT
The only line of input consists of a string S, denoting colors of the candies.

OUTPUT
The minimum number of times Nobita has to use the "Telekinesis Helmet".

CONSTRAINTS
1 <= |S| <= 500
The string consists of lower case letters from the English alphabet.