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()
n=len(s)
k=1
sim=set(s[0])
a=[0]*n
a[0]=1
sim=set(s)
d=dict()
for i in sim:
    d[i]=[-1,1]
for i in range(n):
    d[s[i]][1]=max(d[s[i]][1],i-d[s[i]][0])
    d[s[i]][0]=i
k=10000000
for i in d.values():
    k=min(k,max(n-i[0],i[1]))
print(k)
