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()
mn = 1e9
le = len(s)
for i in range(26):
    c = chr(97 + i)
    pos = s.find(c)
    cur = pos + 1
    if(pos == -1):
        continue
    while(True):
        pos2 = s.find(c, pos + 1)
        if(pos2==-1):
            cur = max(cur, le - pos)
            break
        cur = max(cur, pos2 - pos)
        pos = pos2
    mn = min(cur, mn)
print(mn)
