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
a = [chr(i) for i in range(ord('a'), ord('z') + 1)]
s = input()
min_dom = len(s)
for letter in a:
    if letter in s:
        cur = s.index(letter) + 1
        last = cur - 1
        ll = cur - 1
        for j in range(ll + 1, len(s)):
            if s[j] == letter:
                cur = max(cur, j - last)
                last = j
        min_dom = min(min_dom, max(cur, len(s) - last))
print(min_dom)