Last month, PinkRabbit reached LGM on the competitive programming website Codeforces.

PinkRabbit has now encountered a simple problem, but he is busy browsing Zhihu to take the top spot on the Codeforces world leaderboard, so he has handed the problem over to you:

Given a string $s$ of length $n$ consisting only of lowercase English letters, you need to find the maximum $k$ such that there exist:

$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$

(i.e., the left and right endpoints of the $k$ intervals are strictly increasing and the intervals are pairwise disjoint)

such that for every $1 \le i < k$, $s[l_{i+1} \dots r_{i+1}]$ is a strict substring of $s[l_i \dots r_i]$.

Here, $s[l \dots r]$ denotes the substring of $s$ consisting of the characters from the $l$-th to the $r$-th position.

String $A$ is a strict substring of string $B$ if and only if $A$ can be obtained by deleting some characters from the beginning and the end of $B$ (the number of characters deleted from the beginning and the end can be zero, but the total number of deleted characters must be greater than $0$).

Input

A single string $s$.

Output

A single integer representing the answer.

Examples

Input 1

bbcb

Output 1

2

Note 1

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

Input 2

abcdbcc

Output 2

3

Note 2

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

Input 3

pinkrabbitpinkrtxdytxinkrdynkrabnknealchentxdy

Output 3

6

Constraints

• Subtask 1 (10 points): $n \le 100$
• Subtask 2 (15 points): $n \le 1000$
• Subtask 3 (25 points): $n \le 3 \times 10^4$
• Subtask 4 (30 points): $n \le 10^5$
• Subtask 5 (20 points): No special constraints.

For all data, $1 \le n \le 5 \times 10^5$, and the string contains only lowercase English letters.