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()
indexes = {}

for i in xrange(len(s)):
    if indexes.get(s[i]):
        indexes[s[i]].append(i)
    elif i < (len(s) / 2) + 1:
        indexes[s[i]] = [i]

resp = len(s) / 2 + 1
 
for key in indexes:
    curr = indexes[key]
    value = -1
    if len(curr) > 0:
        for i in xrange(len(curr) - 1):
            value = max(value, curr[i + 1] - curr[i])
        if curr[0] != 0:
            value = max(curr[0] + 1, value)
        if curr[-1] != len(s) - 1:
            value = max(len(s) - curr[-1], value)
        resp = min(resp, value)

if len(s) == 1:
    print 1
else:
    print resp