给定一个由 $n$ 个英文小写字母组成的字符串 $w$。对于满足 $1 \le a \le b \le n$ 的给定位置（即自然数 $a$ 和 $b$），我们定义子串 $w_{a,b}$ 为从字符串 $w$ 的第 $a$ 个位置到第 $b$ 个位置的所有字符顺次连接得到的字符串。我们同样定义剩余部分 $o_{a,b}$ 为从字符串 $w$ 中删除从第 $a$ 个位置到第 $b$ 个位置的所有字符后得到的字符串。
请找出最长的子串 $w_{a,b}$ 的长度，使得剩余部分 $o_{a,b}$ 也包含 $w_{a,b}$ 作为子串。
输入格式
第一行包含给定的字符串 $w$——一个由英文小写字母组成的字符串。
输出格式
输出要求的最大可能长度。
数据范围
设 $n$ 为给定字符串的长度。
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 16 | $1 \le n \le 400$ |
| 2 | 24 | $401 \le n \le 5\,000$ |
| 3 | 60 | $5\,001 \le n \le 100\,000$ |
样例
输入样例 1
abcxyzabc
输出样例 1
3
输入样例 2
bbcdbcbbcbadadda
输出样例 2
5
说明
第二个样例的解释：bbcdbcbbcbadadda $\to$ bbcdbcbadda