题目描述

Snuke 可以按照以下规则，将长度为 $N$ 的字符串 $t$ 转换为长度为 $N - 1$ 的字符串 $t'$：

• 对于每个 $i$（$1 ≤ i ≤ N - 1$），$t'$ 的第 $i$ 个字符必须是 $t$ 的第 $i$ 或第 $(i + 1)$ 个字符。

现在有一个由小写英文字母组成的字符串 $s$。Snuke 的目标是通过重复应用上述操作，使得 $s$ 中的所有字符都相同。请找到达成目标所需的最小操作次数。

约束条件

• $1 ≤ |s| ≤ 100$
• $s$ 由小写英文字母组成。

输入

输入从标准输入读取，格式如下：

$s$

输出

输出达成目标所需的最小操作次数。

示例输入 1

serval

示例输出 1

3

一个可行的解决方案是：serval → srvvl → svvv → vvv。

示例输入 2

jackal

示例输出 2

2

一个可行的解决方案是：jackal → aacaa → aaaa。

示例输入 3

zzz

示例输出 3

0

初始时，$s$ 中的所有字符都相同。

示例输入 4

whbrjpjyhsrywlqjxdbrbaomnw

示例输出 4

8

经过 $8$ 次操作，他可以将 $s$ 变为 rrrrrrrrrrrrrrrrrr。