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()
ll = l = len(s)
for i in range(26):
    d = chr(i+ord('a'))
    t = 0
    if d in s:
        ll = 0
        for i in s:
            t+=1
            if i==d:
                ll = max(t,ll)
                t = 0
        t+=1
        ll = max(t,ll)
    l = min(ll,l)
print(l)

