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 collections import defaultdict

mi = defaultdict(lambda: 100001)
ma = defaultdict(lambda: -1)
mgap = defaultdict(int)
ind = defaultdict(lambda: -1)
s = input()
n = len(s)

for i in range(n):
    if(ind[s[i]] == -1):
        mi[s[i]] = i
        ma[s[i]] = i
        ind[s[i]] = i
    else:
        ma[s[i]] = i
        mgap[s[i]] = max(mgap[s[i]],i - ind[s[i]] - 1)
        ind[s[i]] = i
        
sa = set(ind.keys())
mini = 100001
for i in sa:
    mini = min(mini,max(max(n-1-ma[i],mi[i]),mgap[i]))
print(mini + 1)