题目描述

从一个字符串 $s$ 中选择若干（可以为零）个字符，将其按原先的顺序连接成为一个新字符串，则称其为 $s$ 的一个子序列。

若这个子序列恰好可以被划分为完全相等的两部分，则称其为 $s$ 的一个重复子序列。

例如：空字符串, aa, abab 都是字符串 ababb 的重复子序列，但 aabb 不是。

现在，请你找出给定字符串 $s$ 最长的重复子序列的长度。

输入格式

一行一个字符串 $s$（其长度 $|s|$ 不超过 $5,000$），仅包含小写英文字母。

输出格式

输出一行一个非负整数 $k$，表示 $s$ 最长的重复子序列的长度。

样例

样例输入

ababb

样例输出

4