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
from sys import stdin

s = stdin.readline().strip()
ans = len(s)

for c in range(ord('a'), ord('z') + 1):
    dist, be = 0, -1

    for i, j in enumerate(s):
        if j == chr(c):
            dist = max(dist, i - be)
            be = i

    dist = max(dist, len(s) - be)

    if dist:
        ans = min(ans, dist)
        
print(ans)
