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
def parse(s):
    l=[]
    for i in range(len(s)):
        if s[i] not in l:
            l.append(s[i])
    return l

##def main(cs):
##    l=parse(cs)
##    count=len(l)*[0]
##    for i in range(1,len(cs)+1):
##        for j in range(len(cs)+1-i):
##            for k in range(i):
##                count[l.index(cs[j:j+i][k])]=count[l.index(cs[j:j+i][k])]+1
##        if len(cs)+1-i in count:
##            return i
##        else:
##            count=len(l)*[0]

def main(s):
    l=parse(s)
    counttemp=1
    count=[]
    lc=[]
    for i in range(len(l)):
        for j in range(len(s)):
            if l[i]==s[j]:
                count.append(counttemp)
                counttemp=1
            else:
                counttemp=counttemp+1
        count.append(counttemp)
        lc.append(max(count))
        count=[]
        counttemp=1
    return min(lc)
print(main(input()))
            
