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 long long maxn = 3e5 + 10;
long long N, last[30];
char str[maxn];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> str + 1;
  N = strlen(str + 1);
  vector<long long> v(30, -1);
  for (long long i = 1; i <= N; ++i) {
    long long index = str[i] - 'a';
    v[index] = max(v[index], i - last[index]);
    last[index] = i;
  }
  long long ans = N;
  for (long long i = 0; i < 26; ++i) {
    long long tmp = v[i];
    tmp = max(tmp, N + 1 - last[i]);
    ans = min(ans, tmp);
  }
  cout << ans << endl;
  return 0;
}
