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

st = sys.stdin.readline()
le = len(st) - 1
cind = []
cdif = []
for i in range(26):
    cind.append(-1)
    cdif.append(-1)

for i in range(le):
    c = ord(st[i]) - ord('a')
    cdif[c] = max(i - cind[c], cdif[c])
    cind[c] = i
for i in range(26):
    cdif[i] = max(le - cind[i], cdif[i])

mi = le
for i in range(26):
    if cdif[i] != -1:
        mi = min(cdif[i], mi)

print(mi)