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



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


s = input()
print(k_dominant_character(s))