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.* ;

public class Codeforces{
    public static boolean valid(String s, int target){
        int true_count = 0;
        int[] alpha = new int[26];
        boolean[] check = new boolean[26];
        int num = 0;
        int prev = 0;
        for(int i=0; i< s.length(); i++){
            if(num < target){
                num ++;
                if(alpha[s.charAt(i) - 'a'] == 0){
                    true_count ++;
                    check[s.charAt(i) - 'a'] = true;
                }
                alpha[s.charAt(i) - 'a'] ++;
            }
            else{
                if(s.charAt(i) != s.charAt(prev)){
                    if(alpha[s.charAt(prev) - 'a']-1==0 && check[s.charAt(prev) - 'a']){
                        true_count --;
                        check[s.charAt(prev) - 'a'] = false;
                    }
                    alpha[s.charAt(prev) - 'a'] --;
                    alpha[s.charAt(i) - 'a'] ++;
                }
                prev ++;
            }
            if(num==target && true_count <= 0)
                return false;
        }
        return true;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        String s = in.readLine();
        int l = 0, r = s.length()+1;
        while(l+1 < r){
            int mid = l + (r-l)/2;
            if(valid(s, mid))
                r = mid;
            else
                l = mid;

        }
        out.println(r);
        out.close();

    }

}