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
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Problem888C {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    String s = in.next();
    int l = 0, r = s.length();
    while (l <= r) {
      int mid = l + (r - l) / 2;
      if (f(s, mid)) {
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    System.out.println(l);
  }

  static boolean f(String s, int k) {
    Set<Character> initial = new HashSet<>();
    int[] freq = new int[26];
    CharSequence sequence = s.subSequence(0, k);
    for (int i = 0; i < sequence.length(); i++) {
      freq[sequence.charAt(i) - 'a']++;
      initial.add(sequence.charAt(i));
    }
//    System.out.println("initial = " + initial);
    for (int i = k; i < s.length(); i++) {
      int f = freq[s.charAt(i - k) - 'a'];
      freq[s.charAt(i - k) - 'a']--;
      freq[s.charAt(i) - 'a']++;
//      System.out.println("Removed: " + s.charAt(i - k));
//      System.out.println("Added: " + s.charAt(i));
      if (s.charAt(i - k) != s.charAt(i) && f == 1) {
//        System.out.println("Removing from initial: " + s.charAt(i - k));
        initial.remove(s.charAt(i - k));
        if (initial.isEmpty()) return false;
      }
    }
    return !initial.isEmpty();
  }
}
