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 math import ceil
s=input()
def isgood(k):
    d={}
    q=set(s[:k])
    for x in range(26):
        d[chr(x+ord('a'))]=0
    for x in range(k):
        d[s[x]]+=1
    for x in range(k,len(s)):
        d[s[x-k]]-=1
        d[s[x]]+=1
        tmp=q.copy()
        for y in q:
            if d[y]==0:
                tmp.remove(y)
        q=tmp
        if len(q)==0:
            break
    return len(q)>0
l=0
r=len(s)
while r-l>1:
    mid=ceil((r+l)/2)
    if isgood(mid):
        r=mid
    else:
        l=mid
print(r)