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
s = raw_input().strip()
n = len(s)

last = {}
k = {}
end = {}

for i in xrange(n):
    letter = s[i]
    last_pos = last.get(letter, -1)

    if last_pos == -1:
        end[letter] = n - i
        last[letter] = i
        k[letter] = i + 1
    else:
        end[letter] = n - i
        k[letter] = max(k[letter], i - last_pos)
        last[letter] = i

m = 999999999999
for key in end.keys():
    m = min(m, max(k[key], end[key]))
print m
