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 sys,math 
s=input()
n=len(s)

a=[[0] for i in range(26)]
for i in range(n):
    a[ord(s[i])-97].append(i+1)
for i in range(26):
    a[i].append(n+1)
ans=n+1   
for i in range(26):
    cur=0
    for j in range(1,len(a[i])):
        cur=max(cur,a[i][j]-a[i][j-1])
    ans=min(ans,cur)
print(ans)    