题目描述

原题来自：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$ 次。比如说， ABC 是 ZZABCZZABCZZ 的双子串， ABA 是 ABABA 的双子串（这里的两次出现有重叠部分，这是允许的），而 AAB 不是 AABAB 的双子串。

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

输入格式

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

输出格式

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

qaqaqzz

3

dabcabcabcabca

5

abracadabra

3

数据范围与提示

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

下表为各个 Subtask 的额外限制与得分，空格表示该项无额外限制。你只有通过一个 Subtask 的所有数据才能得到该 Subtask 的分。