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()
A = set()
for i in s:
    A.add(i)
Range = {}

for item in A:
    key = s.find(item)
    Range[item] = key+1
    for i in range(key+1,len(s)):
        if s[i] == item :
            if i - key > Range[item] :
                Range[item] = i - key
            key = i
    if len(s) - key > Range[item] :
            Range[item] = len(s) - key
min = 1000000000
for item in Range.values():
    if item < min :
        min = item
print(min)