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

x = input()

lch = []
lln = {}
lin = {}

for i in range(len(x)) :
	if x[i] in lch :
		lln[x[i]]=max(lln[x[i]],i-lin[x[i]])
		lin[x[i]]=i	
	else :
		lch.append(x[i])
		lln[x[i]]=i+1
		lin[x[i]]=i

for i in range(len(lch)):
	if (lin[lch[i]]!=(len(x)-1)):
		lln[lch[i]]=max(lln[lch[i]],len(x)-lin[lch[i]])

m = lln[lch[0]]
for i in range(1,len(lch)):
	m = min(m,lln[lch[i]])

print(m)