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()

alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

occ = {}
for ltr in alphabet:
    occ[ltr] = [0, len(s)+1]

for i in range(len(s)):
    occ[s[i]].append(i+1)

k = 10**9
for ltr in alphabet:
    kspec = 0
    occ[ltr].sort()
    for i in range(1, len(occ[ltr])):
        kspec = max(kspec, occ[ltr][i] - occ[ltr][i-1])
    k = min(k, kspec)
print(k)
