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 every_seg(A, k, c):
    amount = 0
    for i in range(k - 1):
        if A[i] == c:
            amount += 1
    for i in range(k - 1, len(A)):
        if A[i] == c:
            amount += 1
        if amount == 0:
            return False
        if A[i - k + 1] == c:
            amount -= 1
    return True

S = input()

all_letters = [chr(ord('a') + i) for i in range(26)]

a, b, c = 1, len(S), 0

while a < b:
    c = (a + b) // 2

    if any([every_seg(S, c, letter) for letter in all_letters]):
        b = c
    else:
        a = c + 1

print(a)
