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;
string s;
bool ok(int x) {
  int freq[26], tmp[26];
  fill(freq, freq + 26, 10000000);
  memset(tmp, 0, sizeof(tmp));
  for (int i = 0; i < x; ++i) {
    tmp[s[i] - 'a']++;
  }
  for (int j = x; s[j]; ++j) {
    for (int i = 0; i < 26; ++i) freq[i] = min(freq[i], tmp[i]);
    tmp[s[j] - 'a']++;
    tmp[s[j - x] - 'a']--;
  }
  for (int i = 0; i < 26; ++i) freq[i] = min(freq[i], tmp[i]);
  for (int i = 0; i < 26; ++i)
    if (freq[i]) return true;
  return false;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> s;
  int lo = 0, hi = s.size() - 1;
  while (lo <= hi) {
    int mid = (lo + hi) >> 1;
    if (ok(mid))
      hi = mid - 1;
    else
      lo = mid + 1;
  }
  cout << hi + 1;
  return 0;
}
