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 = str(input())

ab = 'abcdefghijklmnopqrstuvwxyz'
ab_ = [0] * 26
answer = [1000000000] * 26

for i in range(26):
    for j in range(len(s)):
        if s[j] == ab[i]:
            ab_[i] += 1

res = 0
for i in range(26):
    if ab_[i] != 0:
        res += 1

if res == 1:
    print(1)
    exit(0)

for sym in range(26):
    positions = [-1]
    delta = 0

    for i in range(len(s)):
        if s[i] == ab[sym]:
            positions.append(i)

    positions.append(len(s))

    if len(positions) > 1:
        for i in range(len(positions) - 1):
            if (positions[i + 1] - positions[i]) > delta:
                delta = positions[i + 1] - positions[i]
    if delta > 0:
        answer[sym] = delta

print(min(answer))
