Description

给定一个字符串 s ，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 3000。

Format

Input

第1行：1个小写字符串，长度不超过3000个字符

Output

第1行：最长回文子串的长度
第2行：1个字符串，表示最长回文串。如果有多个长度相同的最长回文串，输出位置最靠前的一个。

Samples

babad

3
bab

Limitation

1s, 1024KiB for each test case.

提示

"aba" 也是一个有效答案。但它的位置靠后，不输出