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
# headshot ab >_<
s = input()
hash = dict()
n = len(s)
st = set(list(s))
for i in range(n):
	if s[i] in hash.keys():
		hash[s[i]].append(i+1)
	else:
		hash[s[i]] = [i+1]
ans =  1000000
for i in st:
	k = s.rindex(i)
	li = []
	if n-1 in hash[i] and len(set(list(s)))!=2:
	   hash[i].append(n)
	else:
	  hash[i].append(n+1)
	prev = hash[i][0]
	li.append(hash[i][0])
	for l in hash[i][1:]:
		li.append(l-prev)
		prev = l
	m = max(li)
	ans = min(m,ans)
print(ans)