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
s = raw_input()
pos = [ list() for i in range(26) ]

for i,c in enumerate(s):
	pos[ord(c)-ord('a')].append(i)
l = len(s)

ans = l/2 + 1
for p in pos:
	if not p: continue
	inte = p[0]+1
	for i in xrange(1,len(p)):
		inte = max(p[i]-p[i-1],inte)
	inte = max(l-p[-1], inte)
	ans = min(inte,ans)
	
print ans