408104: GYM102985 K Verbose sandViches

Vicki is eating a sandwich from Vivian's Verbose sandViches. Vivian's sandViches are known for their distinctive lettering: each sandwich comes with a string printed on the top. Vicki has a special way of eating sandViches. She first finds a prefix of the remaining sandVich she has that is a palindrome, and then eats, in one bite, the first half (rounded up) of that palindrome. How many bites does it take Vicki to eat the whole sandwich?

In particular, if the string remaining on her sandVich is $$$s$$$ with characters $$$s_0, s_1, \dots s_n$$$, Vicki identifies some $$$k$$$ such that $$$s_i = s_{k-i}$$$ for $$$0\le i \le k$$$ and bites off $$$s_0, s_1, \dots, s_{\lfloor k/2\rfloor}$$$

A single line containing the string on the sandwich $$$s$$$, where the length of the string is less than $$$10^5$$$.

A single line containing the smallest number of bites required to finish the sandwich

aba

2

ceecd

4

For the first sample input, the first bite Vicki could take could be $$$ab$$$, leaving the sandVich with just $$$a$$$, and then eat the last letter in one bite, for a total of two bites.

For the second, Vicki could eat $$$ce$$$, and then eat each of the last letters individually for a total of $$$4$$$ bites.