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
#####################################   
import atexit, io, sys, collections, math, heapq
buffer = io.BytesIO() 
sys.stdout = buffer
@atexit.register 
def write(): sys.__stdout__.write(buffer.getvalue())   
#####################################
'abacaba'

def f(med,s):
	t = set(map(chr, range(ord('a'), ord('z') + 1)))
	cc = collections.Counter()
	m= 0
	for i in range(len(s)):
		cc[s[i]] +=1
		if i - med >= 0: cc[s[i - med]] -=1
		if i >= med -1:
			m +=1
			tbr = set()
			for key in t:
				if cc[key] == 0:
					tbr.add(key)
			for e in tbr:
				t.remove(e)
			if len(t) == 0:
				return False
	return len(t) > 0
	return any([t[letter] == m for letter in t])


s = raw_input()
lo = 1
hi = len(s)
while( lo < hi): 
	med = (lo + hi) //2 
	if f(med, s):
		hi = med
	else:
		lo = med +1

print lo
