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,stdout
from collections import Counter
from collections import defaultdict
from math import ceil
from bisect import bisect_left 
from bisect import bisect_right
import math

ai = lambda: list(map(int, stdin.readline().split()))
ei = lambda: map(int, stdin.readline().split())
ip = lambda: int(stdin.readline().strip())

s = input()
ans = []
for i in list(set(s)):
	ans += max(map(len,s.split(i)))+1,
print(min(ans))
