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.*;
public class j2{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        char[] str= sc.next().toCharArray();

        int min= Integer.MAX_VALUE;

        for(int i=0;i<26;i++){
            int prev=Integer.MIN_VALUE;
            int max=Integer.MIN_VALUE;
            for(int j=0;j<str.length;j++){
                if(str[j]=='a'+i){
                    int segLen;
                    if(prev<0) 
                        segLen=j;
                    else 
                        segLen=j-prev-1;
                    max=Math.max(max,segLen);
                    prev=j;
                }
            }
            if(prev>=0)
                max=Math.max(max,str.length-prev-1);
            else max=str.length;
            min= Math.min(min, max+1);
        }
        System.out.println(min);

    }

}