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
import sys
import math
from  collections import defaultdict

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

def search(s, n, l):
	rec = [0] * 26
	for i in range(l + 1):
		rec[ord(s[i]) - 97] += 1
	i, j = 0, l
	while j != n - 1:
		j += 1
		rec[ord(s[j]) - 97] += 1 if rec[ord(s[j]) - 97] > 0 else 0
		rec[ord(s[i]) - 97] -= 1
		i += 1
	for i in range(26):
		if rec[i] > 0:
			return True

	return False

def solve(test):
	s = list(input())
	n = len(s)
	if len(set(s)) == 1:
		print(1)
		return
	start = 0
	end = n - 1
	ans = n
	while start <= end:
		mid = (start + end) // 2
		if search(s, n, mid):
			ans = min(ans, mid + 1)
			end = mid - 1
		else:
			start = mid + 1

	print(ans)





if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)

 	 	   					  					 	 	   		  	