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()
l=[]
for i in s:
    if i not in l:
        l.append(i)
minans=len(s)//2+1
bst=-1
bfn=-1
for i in l:
    j=-1
    ans=0
    st=s.find(i,0)
    fn=len(s)-s[::-1].find(i,0)-1
    
    while s.find(i,j+1)!=-1:
        k=j
        
        j=s.find(i,j+1)
        raz=j-k
        ans=max(ans,raz)
        ans=max(ans,max(st+1,len(s)-fn))
    if ans<minans:
        minans=ans

print(minans)
