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
s = list(raw_input())
pos = [[-1] for x in range(26)]
lets = "abcdefghijklmnopqrstuvwxyz"
for i in range(len(s)):
  pos[lets.find(s[i])].append(i)
ans = 999999
for i in range(26):
  pos[i].append(len(s))
  res = -1
  for j in range(len(pos[i])-1):
    res = max(res,pos[i][j+1]-pos[i][j])
  ans = min(res,ans)
print ans