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
input = sys.stdin.readline
from collections import defaultdict

def judge(x):
    cnt = [0]*26
    
    for i in range(x):
        cnt[d[s[i]]] += 1
    
    flag = [True]*26
    
    for i in range(26):
        if cnt[i]==0:
            flag[i] = False
    
    for i in range(x, len(s)):
        cnt[d[s[i]]] += 1
        cnt[d[s[i-x]]] -= 1
        
        for j in range(26):
            if cnt[j]==0:
                flag[j] = False
    
    return True in flag

def binary_search():
    l, r = 1, len(s)
    
    while l<=r:
        mid = (l+r)//2
        
        if judge(mid):
            r = mid-1
        else:
            l = mid+1
    
    return l

s = input()[:-1]
alpha = 'abcdefghijklmnopqrstuvwxyz'
d = defaultdict(int)

for i in range(26):
    d[alpha[i]] = i
    
print(binary_search())