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 sys import stdin
rr = lambda: stdin.readline().strip()
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
def rry(N = None, f = rri):
    for i in xrange(N or rri()):
        yield f()

debug=0
if debug:
    fi = open('t.txt','r')
    rr = lambda: fi.readline().replace('\n','')


def dominant(length):
    for B in A:
        if not B: continue
        cur = -1
        for x in B:
            if x - cur > length:
                break
            cur = x
        else:
            if len(S) - cur <= length:
                return True
    return False

S = rr()
A = [[] for _ in xrange(26)]
for i,x in enumerate(S):
    y = ord(x) - ord('a')
    A[y].append(i)

lo = 0
hi = len(S) + 1
while lo < hi:
    mi = (lo + hi) / 2
    if dominant(mi):
        hi = mi
    else:
        lo = mi + 1
print lo
