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 check(int k) {
  int ch[26] = {0};
  bool c[26] = {false};
  for (int i = 0; i < k; i++) {
    c[s[i] - 'a'] = true;
    ch[s[i] - 'a']++;
  }
  for (int i = k; i < s.size(); i++) {
    ch[s[i - k] - 'a']--;
    ch[s[i] - 'a']++;
    if (ch[s[i - k] - 'a'] == 0) {
      c[s[i - k] - 'a'] = false;
    }
  }
  for (int i = 0; i < 26; i++)
    if (c[i]) return true;
  return false;
}
int main() {
  cin >> s;
  int low = 1, high = (int)s.size(), res = high;
  while (low <= high) {
    int md = (low + high) / 2;
    if (check(md)) {
      res = md;
      high = md - 1;
    } else
      low = md + 1;
  }
  cout << res;
  return 0;
}
