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 collections import defaultdict

s = input()

symbols = defaultdict(list)
for i, c in enumerate(s):
	symbols[c].append(i)

dists = defaultdict(list)
for c, coords in symbols.items():
	deltas = []
	deltas.append(coords[0] + 1)
	for x in range(1, len(coords)):
		deltas.append(coords[x] - coords[x - 1])
	deltas.append(len(s) - coords[-1])
	dists[c] = deltas

# print(dists)

ans = ((len(s) + 2) // 2)
for c in dists.keys():
	if len(dists[c]) > 0:
		ans = min(ans, max(dists[c]))

print(ans)