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
string = raw_input()

dists = {}
letters = {}

i = -1
j = 0
count = 0
while count != len(string) - 1:
    letter = string[j]
    if not letters.has_key(letter):
        letters[letter] = 1
    else:
        letters[letter] += 1
    
    if letters[letter] == 1:
        while j < len(string):
            find = False
            if string[j] == letter:
                dist = abs(j - i)
                if not dists.has_key(string[j]):
                    dists[letter] = dist
                else:
                    if dist > dists[letter]:
                        dists[letter] = dist
                    find = True
                i = j
                j += 1
            else:
                j += 1
    
    if not find and letters[letter] == 1:
        dist = len(string) - i
        if dist > dists[letter]:
            dists[letter] = dist

    count += 1  
    i = -1
    j = count

if len(string) == 1:
    print 1
else:
    print min(dists.values())