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
import math
s=input()
e=set()
for i in s:
    e.add(i)
d={}
for i in e:
    d[i]=[-1]
if len(d)==len(s):
    print (math.ceil((len(s)+1)/2))
    exit()
a=[]
for i in range(len(s)):
    d[s[i]].append(i)
for i in d:
    d[i].append(len(s))
q=-1
ans=1221243214
for i in d:
    q=-1
    for j in range(1,len(d[i])):
        q=max(q,d[i][j]-d[i][j-1])
    ans=min(q,ans)
print(ans)
