Given a string s, please compute the longest sufix of s that is a palindrome, that is, that reads the same backward as forward.

Input

Input consists of several s,
each one made up of between 1 and 10^{6} lowercase letters.

Output

For every s, print the length of the longest sufix of s that is a palindrome.

Public test cases

**Input**

i anna abcbapep zzzzzzzz buenopuesmoltbepuesadios

**Output**

1 4 3 8 1

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++