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;
int conversion(string p) {
  int o;
  o = atoi(p.c_str());
  return o;
}
string toString(int h) {
  stringstream ss;
  ss << h;
  return ss.str();
}
long long gcd(long long a, long long b) { return (b == 0 ? a : gcd(b, a % b)); }
long long lcm(long long a, long long b) { return (a * (b / gcd(a, b))); }
long long toi(string p) {
  long long x;
  istringstream in(p);
  in >> x;
  return x;
}
long long square(long long n) { return n * n; }
long long fastexp(long base, long power) {
  if (power == 0)
    return 1;
  else if (power % 2 == 0)
    return square(fastexp(base, power / 2));
  else
    return base * (fastexp(base, power - 1));
}
bool is_prime(int n) {
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) return 0;
  return 1;
}
int logba(int a, int b) { return log(a) / log(b); }
int main() {
  string x;
  cin >> x;
  int n = (int)x.size();
  int rest = INT_MAX;
  vector<char> S;
  vector<int> P;
  for (char i = 'a'; i <= 'z'; i++) {
    vector<int> M;
    for (int j = 0; j < x.size(); j++) {
      if (x[j] == i) M.push_back(j + 1);
    }
    int maxi = 0;
    for (int j = 1; j < M.size(); j++) maxi = max((M[j] - M[j - 1]), maxi);
    if (M.size() > 1) {
      S.push_back(i);
      P.push_back(maxi);
    }
  }
  for (int i = 0; i < P.size(); i++) {
    bool v = true;
    int tam = P[i];
    char abc = S[i];
    map<char, int> L;
    for (int j = 0; j < tam; j++) L[x[j]]++;
    if (L[abc] <= 0) v = false;
    for (int j = tam; j < n; j++) {
      L[x[j]]++;
      L[x[j - tam]]--;
      if (L[abc] <= 0) v = false;
    }
    if (v)
      rest = min(tam, rest);
    else {
      int last = 0;
      int first = 0;
      for (int j = n - 1; j >= 0; j--) {
        if (x[j] == abc) {
          last = j + 1;
          break;
        }
      }
      for (int j = 0; j < n; j++) {
        if (x[j] == abc) {
          first = j + 1;
          break;
        }
      }
      if ((n - last + 1) >= first)
        rest = min((n - last + 1), rest);
      else
        rest = min(first, rest);
    }
  }
  rest = min(rest, ((int)x.size() / 2 + 1));
  cout << rest << endl;
}
