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 N = 100010;
const int M = 30;
const int INF = 0x3f3f3f3f;
const int iinf = 1 << 30;
const long long linf = 2e18;
const int MOD = 1000000007;
void print(int x) {
  cout << x << endl;
  exit(0);
}
void PRINT(string x) {
  cout << x << endl;
  exit(0);
}
void douout(double x) { printf("%lf\n", x + 0.0000000001); }
int a[M], b[M];
int sum[N][M];
char s[N];
int n;
bool check(int x) {
  for (int i = 1; i <= 26; i++) b[i] = iinf;
  for (int r = x; r <= n; r++) {
    int l = r - x + 1;
    for (int i = 1; i <= 26; i++) a[i] = sum[r][i] - sum[l - 1][i];
    for (int i = 1; i <= 26; i++) b[i] = min(b[i], a[i]);
  }
  for (int i = 1; i <= 26; i++)
    if (b[i]) return true;
  return false;
}
signed main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 26; j++) sum[i][j] = sum[i - 1][j];
    sum[i][s[i] - 'a' + 1]++;
  }
  int l = 0, r = n + 1;
  while (l + 1 < r) {
    int mid = (l + r) >> 1;
    if (check(mid))
      r = mid;
    else
      l = mid;
  }
  printf("%d\n", r);
  return 0;
}
