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;
map<char, int> m;
map<char, int> m1;
set<char> s1;
int main() {
  string s;
  cin >> s;
  int sz = s.size(), mn;
  for (int i = int(0) - (0 > sz); i != (sz) - (0 > sz); i += 1 - 2 * (0 > sz)) {
    m1[s[i]] = max((i + 1) - m[s[i]], m1[s[i]]);
    m[s[i]] = i + 1;
    s1.insert(s[i]);
  }
  if (s1.size() == 1)
    printf("%d\n", 1);
  else if (s1.size() == sz)
    printf("%d\n", (sz / 2) + 1);
  else {
    mn = INT_MAX;
    for (auto it : s1) {
      m1[it] = max((sz - m[it]) + 1, m1[it]);
      mn = min(mn, m1[it]);
    }
    printf("%d\n", mn);
  }
}
