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 = input()
r = 100000
l = 0
dictC = {}
setC = set()
for i in range(97, 97 + 26):
    setC.add(chr(i))
    dictC.update({chr(i): 0}) 

def seach(k, setC, dict1):
    for i in range(0, len(s)):
        dict1[s[i]] += 1         
        if i >= k - 1:
            if i != k - 1:
                dict1[s[i - k]] -= 1
            set2 = set()
            for z in setC:
                if dict1[z] != 0:
                    set2.add(z)
            setC = set2
            if len(setC) == 0:
                return 0
    return 1

while r - l > 1:
    mid = (r + l) // 2
    for i in range(97, 97 + 26):
        dictC.update({chr(i): 0})    
    if seach(mid, setC, dictC) == 1:
        r = mid
    else:
        l = mid
print(r)
    
