Description

给定一个DNA序列:一个由字符A、C、G和T组成的字符串。你的任务是找出序列中最长的重复序列。这是一个只包含一种字符类型的最大长度子字符串。

Format

Input

唯一的输入行包含 n 个字符。

Output

打印一个整数:最长重复次数的长度。

Samples

ATTCGGGA

3

Limitation

• 1 ≤ n ≤ 10^6
• Time limit: 1.00 s
• Memory limit: 512 MB