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
#n=int(input())
l=[ord(i)-97 for i in input()]
maxi={}
n=len(l)
seen={}
for i in range(26):
    seen[i]=-1
for i in range(26):
    maxi[i]=-2347238
#print(seen[2])
for i in range(n):
    maxi[l[i]]=max(maxi[l[i]],i-seen[l[i]])
    seen[l[i]]=i 
for i in range(n):
    maxi[l[i]]=max(maxi[l[i]],n-seen[l[i]])
minim=10000000000000 
#print(maxi)
for i in range(26):
    if i not in l:
        continue
    if maxi[i]<minim:
        minim=maxi[i]
        ans=i 
print(minim)
        