题目描述

原题来自：Codeforces Round #364 (Div. 1) E

大 F 想养猫。

"你喜欢小猫咪吗？" "喵。" "你变成猫了吗？" "喵！"

大 F 喜欢小猫咪，大 F 想养很多很多小猫咪，但是大 F 的想象力十分匮乏，她希望小 F 来帮她为猫咪们取名字。

小 F 也喜欢小猫咪，小 F 也想养许多许多小猫咪，但是小 F 有强迫症，如果养了 $K$ 只猫咪，名字分别是非空字符串 $S_1, S_2, \ldots S_K$，她希望对于所有的 $2 \le i \le K$，$S_i$ 是 $S_{i-1}$ 的双子串。另外，小 F 还希望 $S_1$ 是她自己给定的字符串 $T$ 的子串。

双子串的定义：字符串 $A$ 被称作 $B$ 的双子串，意思是说，$A$ 作为 $B$ 的子串，在 $B$ 中的不同位置出现了至少 $2$ 次。比如说：

$\texttt{ABC}$ 是 $\texttt{ZZABCZZABCZZ}$ 的双子串

$\texttt{ABA}$ 是 $\texttt{ABABA}$ 的双子串（这里的两次出现有重叠部分，这是允许的）

$\texttt{AAB}$ 不是 $\texttt{AABAB}$ 的双子串

小 F 想养尽量多的猫咪，所以小 F 想要找到尽量大的 $K$，使得存在 $S_1, S_2, \ldots, S_K$ 满足条件。

输入格式

一行一个字符串 $T$，仅含小写字母。

输出格式

一个整数，可能的 $K$ 的最大值。

qaqaqzz

3

解释： $S_1 = \texttt{qaqaqzz}$ $S_2 = \texttt{qaq}$ $S_3 = \texttt{q}$

dabcabcabcabca

5

解释： $S_1 = \texttt{abcabcabcabca}$ $S_2 = \texttt{abcabcabca}$ $S_3 = \texttt{abcabca}$ $S_4 = \texttt{abca}$ $S_5 = \texttt{a}$

abracadabra

3

解释： $S_1 = \texttt{abracadabra}$ $S_2 = \texttt{abra}$ $S_3 = \texttt{a}$

数据规模与约定

数据范围与提示

对于所有数据，保证 $1 \le N = |T| \le 2 \times 10^5$，$T$ 仅包含小写字母。

下表为各个 Subtask 的详细限制与分值分布：