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.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/**
 *
 * @author arabtech
 */
public class KDominant {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String t = sc.next();
        int diff = 0;
        int length = 0;
        int current = 0;
        int k = 0;
        int start = 0;
        ArrayList<Integer> diffLetters = new ArrayList<>();
        ArrayList<Integer> len = new ArrayList<>(26);
        boolean[] checked = new boolean[150];
        for (int i = 0; i < t.length(); i++) {
            int c = t.charAt(i);
            if (checked[c] == false) {
                checked[c] = true;
                diff++;
                diffLetters.add(c);
            }
        }
        if (diff == t.length()) {
            System.out.println((t.length() / 2) + 1);
        } else if (diff == 1) {
            System.out.println(1);
        } else {
            len.add(1);
            while (!diffLetters.isEmpty()) {
                start = 0;
                length = 0;
                current = diffLetters.get(0);
                diffLetters.remove(0);
                for (int i = 0; i < t.length(); i++) {
                    int l = t.charAt(i);
                    if (l != current) {
                        length++;
                        if (i == t.length() - 1) {
                            if (len.get(k) < length ) {
                                len.set(k, length );
                            }
                        }
                    } else if (l == current) {
                        if (i == 0) {
                            start = 1;
                        }
                        if (start == 0) {
                            length++;
                            start = 1;
                        }
                        if (length != 0 && length != 1) {
                            if (len.size() == k) {
                                len.add(k, length);
                            } else {
                                if (len.get(k) < length) {
                                    len.set(k, length);
                                    length = 0;
                                }
                            }
                        }
                        length = 1;
                    }

                }
                k++;
            }
            System.out.println(Collections.min(len));
        }
    }

}
