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
from collections import defaultdict
s=input()
d={}
d=defaultdict(lambda:[0],d)

d1={}
d1=defaultdict(lambda:-1,d1)

k=1
for i in s:
    d1[i]=max(k-d[i][-1],d1[i])
    d[i].append(k)
    k+=1

#print(d)
#print(d1)
ans=[]
for i in d.keys():
    d1[i]=max(len(s)-d[i][-1]+1,d1[i])
    
for i in d1.keys():
    if len(d[i])>2:
        ans.append(d1[i])

if len(ans)==0:
    print(len(s)//2+1)
else:
    print(min(min(ans),len(s)//2+1))
