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
#include <bits/stdc++.h>
using namespace std;
template <typename T, typename S>
inline bool upmin(T& a, const S& b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S>
inline bool upmax(T& a, const S& b) {
  return a < b ? a = b, 1 : 0;
}
char s[100010];
int len, ans = 0x3f3f3f3f;
int pos[210], ma[210];
int main() {
  scanf("%s", s + 1);
  len = strlen(s + 1);
  for (int i = 1; i <= len; i++) {
    int p = pos[s[i]];
    upmax(ma[s[i]], i - p);
    pos[s[i]] = i;
  }
  for (int i = 'a'; i <= 'z'; i++) upmax(ma[i], len + 1 - pos[i]);
  for (int i = 'a'; i <= 'z'; i++) upmin(ans, ma[i]);
  cout << ans << endl;
  return 0;
}
