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 long long inf = 1000000000;
const long long mod = 1000000007;
template <class T, class It>
void readvector(vector<T>& __cur, It& __cnt) {
  for (It ind = 0; ind < __cnt; ind++) {
    cin >> __cur[ind];
  }
}
template <class T>
T lcm(T a, T b) {
  return abs(a * b) / __gcd(a, b);
}
string s;
bool check(long long k) {
  unordered_map<char, long long> cur;
  unordered_set<char> common;
  for (int i = 0; i < k; i++) {
    cur[s[i]]++;
    common.insert(s[i]);
  }
  for (long long i = k; i < s.size(); i++) {
    if (cur[s[i]] != 0) {
      cur[s[i]]++;
      common.insert(s[i]);
    }
    if (cur[s[i - k]] > 0) cur[s[i - k]]--;
    if (cur[s[i - k]] == 0) {
      common.erase(s[i - k]);
    }
  }
  return !common.empty();
}
int main() {
  cin >> s;
  long long l = 0, r = s.size() + 1;
  while (r - l > 1) {
    long long mid = (l + r) / 2;
    if (check(mid)) {
      r = mid;
    } else {
      l = mid;
    }
  }
  cout << r;
  return 0;
}
