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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// Educational Codeforces Round 32
// K-Dominant Character
public class Problem_888_C {

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        String st = in.next();
        int res = Integer.MAX_VALUE;
        for (char ch = 'a'; ch <= 'z'; ch++) {
            res = Math.min(res, calcMaxDist(st, ch));
        }
        System.out.println(res);
    }

    private static int calcMaxDist(String st, char ch) {
        if (st.length() == 1) {
            return 1;
        }
        int prev = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < st.length(); i++) {
            char stCh = st.charAt(i);
            if (ch == stCh) {
                max = Math.max(max, i - prev);
                prev = i;
            }
        }
        max = Math.max(st.length() - prev, max);
        return max;
    }

    public static class InputReader {

        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }

}
