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;
int main() {
  pair<int, int> arr[26];
  string str;
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> str;
  for (int i = 0; i < 26; i++) {
    arr[i] = make_pair(0, 0);
  }
  for (char ch : str) {
    for (int i = 0; i < 26; i++) {
      arr[i].second++;
    }
    int at = ch - 'a';
    arr[at].first = max(arr[at].first, arr[at].second);
    arr[at].second = 0;
  }
  for (int i = 0; i < 26; i++) {
    arr[i].second++;
  }
  int least = str.length() + 100;
  for (int i = 0; i < 26; i++) {
    arr[i].first = max(arr[i].first, arr[i].second);
    if (arr[i].first < least) least = arr[i].first;
  }
  cout << least << "\n";
}
