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;
template <class X, class Y>
void amax(X& x, const Y& y) {
  if (x < y) x = y;
}
template <class X, class Y>
void amin(X& x, const Y& y) {
  if (x > y) x = y;
}
const int INF = 1e9 + 10;
const long long INFL = 1e18 + 10;
const int MAX = 1e5 + 10;
string s;
int nxt[MAX], prv[MAX];
int dist[30], last[30];
void process() {
  cin >> s;
  memset(last, 255, sizeof(last));
  for (int i = 0; i < s.size(); i++) {
    int c = s[i] - 'a';
    prv[i] = last[c];
    last[c] = i;
  }
  for (int i = 0; i < 26; i++) last[i] = s.size();
  for (int i = s.size() - 1; i >= 0; i--) {
    int c = s[i] - 'a';
    nxt[i] = last[c];
    last[c] = i;
  }
  memset(dist, 255, sizeof(dist));
  for (int i = 0; i < s.size(); i++) {
    int c = s[i] - 'a';
    amax(dist[c], i - prv[i]);
    amax(dist[c], nxt[i] - i);
  }
  int res = s.size();
  for (int i = 0; i < 26; i++)
    if (dist[i] != -1) amin(res, dist[i]);
  cout << res;
}
int main() {
  ios_base::sync_with_stdio(false);
  process();
}
