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;
char s[101000];
int len;
bool chick(int mid) {
  int b1[27], num[27];
  memset(b1, 0, sizeof(b1));
  memset(num, 0, sizeof(num));
  for (int i = 0; i < mid; i++) {
    b1[s[i] - 'a']++;
    num[s[i] - 'a'] = 1;
  }
  for (int i = 1; i + mid - 1 < len; i++) {
    b1[s[i - 1] - 'a']--;
    b1[s[i + mid - 1] - 'a']++;
    for (int j = 0; j < 26; j++) {
      if (b1[j]) num[j]++;
    }
  }
  for (int i = 0; i < 26; i++)
    if (num[i] == len - mid + 1) return 1;
  return 0;
}
int main() {
  while (scanf("%s", s) != EOF) {
    len = strlen(s);
    int l, r;
    l = 1;
    r = len;
    int ans = len;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (chick(mid)) {
        ans = mid;
        r = mid - 1;
      } else
        l = mid + 1;
    }
    cout << ans << endl;
  }
  return 0;
}
