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 = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fll;
const long long MAX = (long long)1e5 + 10;
int main() {
  string second;
  cin >> second;
  int n = second.size();
  int h[26], d[26];
  for (int i = 0; i < 26; i++) {
    d[i] = 0;
    h[i] = -1;
  }
  for (int i = 0; i < n; i++) {
    if (d[second[i] - 'a'] < i - h[second[i] - 'a']) {
      d[second[i] - 'a'] = i - h[second[i] - 'a'];
    }
    h[second[i] - 'a'] = i;
  }
  int minn = INF;
  for (int i = 0; i < 26; i++) {
    if (d[i] < n - h[i]) {
      d[i] = n - h[i];
    }
    minn = min(minn, d[i]);
  }
  cout << minn << endl;
  return 0;
}
