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 check(s, m):
    for c in range(ord('a'), ord('z') + 1):
        cnt = 0
        for i in range(0, m):
            if s[i] == chr(c):
                cnt += 1
        if cnt == 0:
            continue
        flag = True
        for i in range(m, len(s)):
            if s[i - m] == chr(c):
                cnt -= 1
            if s[i] == chr(c):
                cnt += 1
            if cnt == 0:
                flag = False
                break
        if flag == True:
            return True
    return False

s = input()
l = 0
r = len(s)
while l + 1 < r:
    m = l + ((r -l) >> 1)
    if check(s, m) == True:
        r = m
    else:
        l = m
print(r)