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 = list(input())
c = 97
ans = 999999
for i in range(26):
    pr = -1
    p = 0
    p = chr(c)
    ##print(p, end=' ')
    c += 1
    le = -1
    for j in range(len(s)):
        log = True
        if p == s[j]:
            if j - (pr+1) > le:
                le = j - (pr+1)
                #print(p,j,pr+1,le)##
##            if p == "g":
##                print(p, le, j, pr)
            pr = j
            log = False
        if j == len(s)-1 and j - (pr) > le and log:
            le = j - (pr)
##            if p == "g":
##                print(p, le, j, pr)
    if ans > le + 1 and le > -1:
        ans = le + 1
    ##print(le, p)##
print(ans)
