上个月，PinkRabbit 在算法竞赛网站 Codeforces 一把打上了 LGM。

PinkRabbit 现在看到了一道简单题，但他忙于水知乎夺取 Codeforces 世界榜首，于是把问题交给了你：

给定一个长度为 $n$ 的只包含小写英文字母的字符串 $s$，你需要找到一个最大的 $k$，使得存在：

$1 \le l_1 \le r_1 < l_2 \le r_2 < l_3 \le r_3 < \dots < l_k \le r_k \le n$

（即 $k$ 个区间 $[l_i, r_i]$ 的左右端点都递增且两两不相交）

使得对于每个 $1 \le i < k$，都满足 $s[l_{i+1} \dots r_{i+1}]$ 是 $s[l_i \dots r_i]$ 的严格子串。

其中 $s[l \dots r]$ 表示字符串 $s$ 的第 $l$ 到第 $r$ 个字符组成的字符串。

字符串 $A$ 是字符串 $B$ 的严格子串，当且仅当从 $B$ 的开头和结尾各删掉若干个字符（从开头和结尾删掉的字符个数都可以是零个，但删掉的字符个数之和必须大于 $0$）能够得到 $A$。

输入格式

一行一个字符串 $s$。

输出格式

一行一个整数表示答案。

样例

样例输入 1

bbcb

样例输出 1

2

说明 1

$l_1 = 1, r_1 = 2, l_2 = 4, r_2 = 4$

样例输入 2

abcdbcc

样例输出 2

3

说明 2

$l_1 = 1, r_1 = 4, l_2 = 5, r_2 = 6, l_3 = 7, r_3 = 7$

样例输入 3

pinkrabbitpinkrtxdytxinkrdynkrabnknealchentxdy

样例输出 3

6

数据范围

子任务 1 (10 分)：$n \le 100$； 子任务 2 (15 分)：$n \le 1000$； 子任务 3 (25 分)：$n \le 3 \times 10^4$； 子任务 4 (30 分)：$n \le 10^5$； 子任务 5 (20 分)：无特殊限制。

对于所有的数据，有 $1 \le n \le 5 \times 10^5$，字符串仅包含小写英文字母。