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
from collections import defaultdict

s = str(raw_input())
alpha = 'abcdefghijklmnopqrstuvwxyz'
d = defaultdict(list)

for i in alpha:
    d[i].append(0)
for i in range(len(s)):
        d[s[i]].append(1+i)
for i in alpha:
    d[i].append(len(s)+1)

def check(l,s,k):
    s = l + s + l
    for i in range(1,len(d[l])):
        if d[l][i] - d[l][i-1] > k:
            return False
    return True

def best(l):
    L = 1
    R = len(s)+1
    while True:
        k = (L+R)/ 2
        if check(l,s,k):
            R = k-1
            if not check(l,s,k-1):
                return k
        else:
            L = k+1

mini = len(s)+1
for l in alpha:
    if best(l) < mini:
        mini = best(l)
print mini