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
import math
from sys import stdin
index=0
string=stdin.readline().strip()
L=len(string)
letterList=[]
position=defaultdict(list)
output=L
for letter in string:
    letterList.append(letter)
    position[letter].append(index)
    index+=1
for key in position:
    position[key].insert(0,-1)
    position[key].append(L)
    lm=0
    for i in range(len(position[key])-1):
        length=position[key][i+1]-position[key][i]
        if length>lm:
            lm=length

    if lm<output:
        output=lm

print (output)


    