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;
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  string a;
  cin >> a;
  set<char> s;
  long long n = a.length();
  map<char, vector<long long> > mm;
  for (long long i = 0; i < n; ++i) {
    mm[a[i]].push_back(i);
    s.insert(a[i]);
  }
  for (auto i : s) {
    mm[i].push_back(-1);
    mm[i].push_back(n);
    sort(mm[i].begin(), mm[i].end());
  }
  long long mn = 1e9;
  for (auto i : mm) {
    long long mx = 0;
    long long k = i.second.size();
    for (long long j = 0; j < k - 1; j++) {
      mx = max(mx, i.second[j + 1] - i.second[j]);
    }
    mn = min(mx, mn);
  }
  cout << mn;
}
