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

def good(s, k):
    for j in range(26):
        c = chr(ord('a') + j)
        ok = True
        count = 0
        for i in range(len(s)):
            if s[i] == c:
                count += 1
            if i - k >= 0 and s[i - k] == c:
                count -= 1
            if i + 1 >= k and count == 0:
                ok = False
                break
        if ok:
            return True
    return False


def solve(s):
    low = 0
    high = len(s)
    while low + 1 < high:
        mid = (low + high) // 2
        if good(s, mid):
            high = mid
        else:
            low = mid
    return high


s = input()
print(solve(s))