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>
char a[100005];
int b[27];
int max(int a, int b) {
  if (a > b)
    return a;
  else
    return b;
}
int min(int a, int b) {
  if (a < b)
    return a;
  else
    return b;
}
int main() {
  scanf("%s", a);
  memset(b, 0, sizeof(b));
  int l = strlen(a);
  int k = l / 2 + 1;
  for (int i = 0; i < l; i++) {
    int c = a[i] - 96;
    b[c]++;
  }
  for (int j = 1; j < 27; j++) {
    if (b[j] > 1) {
      int i, e, k1;
      char d = 96 + j;
      for (i = 0; i > l && d != a[i]; i++)
        ;
      e = i - 1;
      k1 = i;
      for (; i < l; i++) {
        if (a[i] == d) {
          k1 = max(k1, i - e);
          e = i;
        }
      }
      k1 = max(k1, l - e);
      k = min(k, k1);
    }
  }
  printf("%d\n", k);
  return 0;
}
