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
s = input()
a = set()
for char in s:
    a.add(char)
ans = list()
for i in a:
    n = list()
    n.append(-1)
    n.append(s.__len__())
    for j in range(0, s.__len__()):
        if i == s[j]:
            n.append(j)
    r = list()
    n = sorted(n)
    for j in range(1, n.__len__()):
        r.append(abs(n[j]-n[j-1]))
    ans.append((sorted(r)[-1]))
print(sorted(ans)[0])