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;
const int A = 1e5 + 10;
char s[A];
int n;
char aim;
bool check(int len) {
  int cnt = 0;
  for (int i = 0; i < len; i++) {
    if (s[i] == aim) cnt++;
  }
  if (!cnt) return false;
  for (int i = len; i < n; i++) {
    if (s[i] == aim) cnt++;
    if (s[i - len] == aim) cnt--;
    if (!cnt) return false;
  }
  return true;
}
int main() {
  scanf("%s", s);
  n = strlen(s);
  int ans = n;
  for (int i = 0; i < 26; i++) {
    aim = 'a' + i;
    int l = 1, r = n, res = n;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (check(mid)) {
        res = mid;
        r = mid - 1;
      } else
        l = mid + 1;
    }
    ans = min(ans, res);
  }
  printf("%d\n", ans);
  return 0;
}
