Longest palindromic substring

Find the length of the longest contiguous substring of S that reads the same forwards and backwards.

Medium7StringBinary searchHash mapNo attempts yetTime limit0.5sMemory limit512 MB

Description

Examples5

Problem

A palindrome is a string that reads the same forwards and backwards. For example, a, aa, and aba are palindromes, while ab is not.

Given a string $S$ , write a program that finds the length of the longest palindromic substring of $S$ . A substring here is a contiguous block of characters cut out of $S$ .

Input

The first line contains the string $S$ . $S$ consists of lowercase letters only, and its length is at least 1 and at most 100,000.

Output

Print the length of the longest palindromic substring on the first line.