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 inf_int = 1e9;
const long long inf_ll = 1e18;
const int MAXN = (2e5 + 500);
const int MOD = 1e9 + 7;
bool debug = 0;
bool val[26];
string s;
int cnt[26];
bool ok(int x) {
  memset(val, 1, sizeof val);
  memset(cnt, 0, sizeof cnt);
  for (int i = 0; i < x; ++i) {
    cnt[s[i]]++;
  }
  for (int i = 0; i < 26; ++i) {
    if (cnt[i] == 0) val[i] = 0;
  }
  for (int i = x; i < ((int)s.size()); ++i) {
    cnt[s[i]]++;
    cnt[s[i - x]]--;
    if (cnt[s[i - x]] == 0) {
      val[s[i - x]] = 0;
    }
  }
  bool flag = 0;
  for (int i = 0; i < 26; ++i) flag |= val[i];
  return flag;
}
void solve() {
  cin >> s;
  int n = ((int)s.size());
  for (char &c : s) c -= 'a';
  int l = 1, r = n;
  int ans = -1;
  while (l <= r) {
    int m = (l + r) >> 1;
    if (ok(m)) {
      ans = m;
      r = m - 1;
    } else {
      l = m + 1;
    }
  }
  assert(ans >= 1);
  cout << ans << endl;
}
int main() {
  int t = 1;
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  while (t--) solve();
}
