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

ans = []

for c in set(list(word)):
    maior_dist = 0
    atual_dist = 0
    last_pos = 0
    for i, let in enumerate(word):
        if let == c:
            atual_dist += 1
            if atual_dist > maior_dist: maior_dist = atual_dist
            atual_dist = 0
            last_pos = i
        else:
            atual_dist += 1
    if atual_dist > maior_dist: maior_dist = atual_dist

    ans.append(max(maior_dist, len(word) - last_pos))

print(min(ans))
