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
line = input()
d = {}
dist = {}
for i in range(len(line)):
    elem = line[i]
    if elem not in d:
        d[elem] = i
        dist[elem] = i + 1
    else:
        dist[elem] = max(dist[elem], i - d[elem])
        d[elem] = i
    #print(dist)
minimum = 999999999
for key in dist:
    dist[key] = max(dist[key], len(line) - d[key])
    minimum = min(minimum, dist[key])
print(minimum)