Longest Palindromic Substring

Given a lowercase string of up to 100,000 characters, report the length of its longest palindromic substring.

Medium7StringString matchingDynamic programmingTwo pointersInterviewNo attempts yetTime limit2sMemory limit512 MB

Description

Examples5

Problem

You are given a string $S$ consisting only of lowercase English letters. Write a program that finds the length of the longest substring of $S$ that is a palindrome.

A palindrome is a string that reads the same forward and backward. A substring is a contiguous part of $S$ .

Input

The first line contains the string $S$ , consisting only of lowercase English letters. The length of $S$ is at most $100\,000$ .

Output

Print the length of the longest substring of $S$ that is a palindrome.