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, exit, setrecursionlimit
from collections import deque
input = stdin.readline
lmi = lambda: list(map(int, input().split()))
mi = lambda: map(int, input().split())
si = lambda: input().strip('\n')
ssi = lambda: input().strip('\n').split()
mod = 10**9+7

def check(k):
    ok = [False for i in range(26)]
    cnt = [0 for i in range(26)]
    for i in range(k):
        ok[ord(s[i])-ord("a")] = True
        cnt[ord(s[i]) - ord("a")] += 1
    for i in range(k, len(s)):
        cnt[ord(s[i]) - ord("a")] += 1
        cnt[ord(s[i-k]) - ord("a")] -= 1
        if cnt[ord(s[i-k]) - ord("a")] == 0:
            ok[ord(s[i - k]) - ord("a")] = False
    for i in ok:
        if i:
            return True
    return False
s = si()
l = 0
r = len(s)
while l < r:
    mid = l + r >> 1
    if check(mid):
        r = mid
    else:
        l = mid+1
print(l)