You are given a string s consisting of lowercase Latin letters. Character c is called k-dominant iff each substring of s with length at least k contains this character c.

You have to find minimum k such that there exists at least one k-dominant character.

Input

The first line contains string s consisting of lowercase Latin letters (1 ≤ |s| ≤ 100000).

Output

Print one number — the minimum value of k such that there exists at least one k-dominant character.

Examples

Input

abacaba


Output

2


Input

zzzzz


Output

1


Input

abcde


Output

3
from sys import exit
from itertools import permutations

# xs = map(int, raw_input().split(' '))

s = raw_input()

min_max_gap = 10000000

for i_c in xrange(ord('a'), ord('z') + 1):
    c = chr(i_c)

    max_gap = 1

    prev_occurrence = -1

    for i, d in enumerate(s):
        if d == c:
            gap = i - prev_occurrence

            if gap > max_gap:
                max_gap = gap

            prev_occurrence = i

    gap = len(s) - prev_occurrence

    if gap > max_gap:
        max_gap = gap

    if max_gap < min_max_gap:
        min_max_gap = max_gap

print min_max_gap
