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()
lenString = len(string)
lettersMap = {}
k = lenString
kResult = lenString
for i in range(lenString):
    if(string[i] not in lettersMap):
        positions = [i+1]
        for j in range(i+1, lenString):
            if(string[j] == string[i]):
                positions.append(j+1)
        for x in range(len(positions)):
            if(x == 0):
                k = positions[x]
            elif(positions[x] - positions[x-1] > k):
                k = positions[x] - positions[x-1]
            if(x == len(positions) - 1 and (lenString - positions[x] + 1) > k):
                    k = (lenString - positions[x]) + 1
        lettersMap[string[i]] = positions
        if(k < kResult):
            kResult = k

print(kResult)