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
def possible(s,k):
	candidates = set(s[:k])
	count = {}
	for c in s[:k]:
		if c not in count:
			count[c] = 0
		count[c] += 1

	for i in range(k,len(s)):
		count[s[i-k]] -= 1
		if s[i] not in count:
			count[s[i]] = 0
		count[s[i]] += 1
		if count[s[i-k]]==0 and s[i-k] in candidates:
			candidates.remove(s[i-k])
	return len(candidates) > 0

def bs(s): #find the smallest k s.t. there is a k-dominant character
	L = 1
	R = len(s)
	while R-L > 1:
		M = (L+R)//2
		if possible(s,M):
			R = M
		else:
			L = M
	for ans in range(L,R+1):
		if possible(s,ans):
			return ans
	return -1

print(bs(input()))