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.InputStreamReader;
import java.util.Arrays;

public class KDominantCharacter {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] a = br.readLine().toCharArray();
        int n = a.length;

        //The length of the k-dominant substring for a char C is the max length between two Cs
        //Store previous position for the character as you iterate
        //Store the max gap for that character in the gap[]
        //Iterate over the gap[] to find the char with minimum gap i.e. minimum substring

        int[] prevPos = new int[26];
        int[] gap = new int[26];

        //initialize prevPos with -1 to account for the gap of the 1st occurrence
        Arrays.fill(prevPos, -1);

        //note that in the following loop, last occurrence is not accounted for
        for(int i=0; i<n; i++){
            int index = a[i] - 'a';
            int gp = i - prevPos[index];
            if(gp > gap[index]){
                gap[index] = gp;
            }
            prevPos[index] = i;
        }

        //iterate over gap to find min k-dominant substring
        int minSubstr = n;
        for(int i=0; i<26; i++){
            if(prevPos[i] != -1){
                //For the last occurrence, the gap will be n-prevPos
                //Take the max gap for the max length between two occurrences of the character
                int maxGap = Math.max(gap[i], n-prevPos[i]);

                //Take the min of the max gaps for the smallest substring
                if(maxGap < minSubstr){
                    minSubstr = maxGap;
                }
            }
        }
        System.out.println(minSubstr);
    }
}
