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

count = {}
prev_index = {}
for i in range(len(string)):
    current = string[i]
    if current in count:
        count[current] = max(count[current], i - prev_index[current])
    else:
        count[current] = i + 1

    prev_index[current] = i

for i in string:
    # print(i, count[i], max(count[i], len(string) - prev_index[i]))
    count[i] = max(count[i], len(string) - prev_index[i])

print(min(count.values()))