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
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

s = minp()
a = [-1]*26
M = [0]*26
for i in range(len(s)):
	z = ord(s[i])-ord('a')
	M[z] = max(M[z], i-a[z])
	a[z] = i
for i in range(26):
	M[i] = max(M[i], len(s)-a[i])
print(min(M))