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 i, i0, n, m;
char a[100005];
int main() {
  scanf("%s", a);
  int ans = 9999999, len = strlen(a);
  for (i = 'a'; i <= 'z'; i++) {
    int p0 = 0, p = -1;
    for (i0 = 0; i0 < len; i0++) {
      if (a[i0] == i) {
        p0 = max(p0, i0 - p);
        p = i0;
      }
    }
    p0 = max(p0, i0 - p);
    ans = min(ans, p0);
  }
  printf("%d\n", ans);
  return 0;
}
