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

public final class KDominantCharacterCF {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s=sc.next();
        int n=s.length();
        int left=1,right=n;
        int ans=Integer.MAX_VALUE;
        while (left<=right){
            int mid=left+(right-left)/2;
            //System.out.println(mid);
            if(isThere(s,mid)){
                ans=mid;
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        System.out.println(ans);
    }

    private static boolean isThere(String s, int mid) {

        int count[]=new int[26];
        boolean isTrue[]=new boolean[26];
        int falseCount=0;
        Arrays.fill(isTrue,true);
        for(int i=0;i<mid;i++){
            int index=s.charAt(i)-97;
            count[index]++;
        }
        for(int i=0;i<26;i++){
            if(count[i]==0){
                isTrue[i]=false;
                falseCount++;
            }
        }
        int i=mid;
        while (i<s.length()){
            int index1=s.charAt(i)-97;
            int index2=s.charAt(i-mid)-97;
            count[index1]++;
            count[index2]--;

            if(count[index2]<=0){
                if(isTrue[index2]){
                    isTrue[index2]=false;
                    falseCount++;
                }
            }
            if(falseCount==26) return false;
            i++;
        }
        return true;
    }
}
