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
a = input()
l = len(a)
from collections import defaultdict
b = defaultdict(list)
for i in range(l):
    b[ord(a[i])-97].append(i)
p = []
for z in b:
    i = b[z]
    k = len(i)
    d = []
    d.append(i[0]+1)
    for j in range(1,k):
        d.append(i[j]-i[j-1])
    d.append(l-i[k-1])
    p.append(max(d))
print(min(p))
