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
from sys import stdin


def main():
	s = stdin.readline()
	size = len(s) - 1
	ans = size
	for i in range(26):
		low = 0
		high = size
		curr_ch = i
		while low < high:
			mid = (low + high) // 2
			count = 0
			for j in range(mid):
				if ord(s[j]) - ord('a') == curr_ch:
					count += 1
			if count == 0:
				ok = False
			else:
				ok = True
				for j in range(mid, size):
					if ord(s[j - mid]) - ord('a') == curr_ch:
						count -= 1
					if ord(s[j]) - ord('a') == curr_ch:
						count += 1
					if count == 0:
						ok = False
						break
			if ok:
				high = mid
			else:
				low = mid + 1
		ans = min(ans, low)
	print(ans)
	

if __name__ == '__main__':
	main()
