Description

对于字符串 W，定义W^R^为W反序后的字符串。先给定字符串S，求S的最大子串能表示成WW^R^WW^R^的形式。

S长度小于等于300000

Format

Input

Output

Samples

2
abrahellehhelleh
rachelhellabracadabra

12
0