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;
#pragma comment(linker, "/stack:200000000")
int t, n, m, j, ans, k, a, b, c, d, e, f, sum, i, sz, lo, hi, mid, q, le, re;
string s, s2, s3, s4;
int ar[(int)(1e6 + 10)], ar2[(int)(1e6 + 10)];
char ch;
void brainfuck();
bool finder(int x);
int main() {
  ios_base::sync_with_stdio(NULL);
  cin.tie(NULL);
  cout.tie(NULL);
  brainfuck();
  return 0;
}
void brainfuck() {
  cin >> s;
  n = s.size();
  lo = 1, hi = n;
  for (i = 0; i < n - 1; i++) {
    if (s[i] == s[i + 1])
      a = 1;
    else {
      a = 0;
      break;
    }
  }
  if (a || s.size() == 1) {
    cout << "1";
    return;
  }
  while (lo <= hi) {
    mid = (lo + hi) / 2;
    if (finder(mid)) {
      ans = mid;
      hi = mid - 1;
    } else
      lo = mid + 1;
  }
  cout << ans;
}
bool finder(int x) {
  b = 1;
  for (j = 0; j <= 25; j++) {
    ch = j + 'a';
    a = 0;
    le = 0;
    for (i = 0; i < n; i++) {
      if (s[i] == ch) a++;
      if (i - le + 1 > x) {
        if (s[le] == ch) a--;
        le++;
      }
      if (i - le + 1 == x && !a) {
        b = 1;
        break;
      }
    }
    if (i == n) return 1;
  }
  return 0;
}
