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.Scanner;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String text = in.next();
            if (text == null || text.length() < 2) {
                System.out.println(text.length());
            } else {
                int len = text.length();
                HashMap<Character, Integer> lastPos = new HashMap<>();
                HashMap<Character, Integer> longestInt = new HashMap<>();
                char[] arr = text.toCharArray();
                int lastP;
                for (int i = 0; i < len; ++i) {
                    lastP = lastPos.getOrDefault(arr[i], -1);
                    lastPos.put(arr[i], i);
                    if (!longestInt.containsKey(arr[i]) || longestInt.get(arr[i]) < (i - lastP)) {
                        longestInt.put(arr[i], i - lastP);
                    }
                }
                for (Map.Entry<Character, Integer> item : lastPos.entrySet()) {
                    Character ch = item.getKey();
                    lastP = len - item.getValue();

                    if (!longestInt.containsKey(ch) || longestInt.get(ch) < lastP) {
                        longestInt.put(ch, lastP);
                    }
                }
                lastP = Integer.MAX_VALUE;
                for (Map.Entry<Character, Integer> item : longestInt.entrySet()) {
                    if (item.getValue() < lastP) {
                        lastP = item.getValue();
                    }
                }
                System.out.println(lastP);
            }
        }
    }
}