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
seq = input()
n = len(seq)
s = set(seq)
dic = dict()
for i in s:
	dic[i] = [0,0]
#print(dic)
for i in range(n):
	c = seq[i]
	if (i +1 - dic[c][0] > dic[c][1]):
		dic[c][1] = i+1 - dic[c][0]
	dic[c][0]= i +1

mi = 100000
for i in s:
#	print(n - dic[i][0] , dic[i][1])
#	print(i,n)
	if (n - dic[i][0] +1> dic[i][1]):
		dic[i][1] = n - dic[i][0] +1
	if(dic[i][1] < mi):
		mi= dic[i][1]


print(mi)