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.*;
import java.io.*;
public class Solution{
	public static void main(String args[])throws Exception{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String s=br.readLine();
        int lastPos[]=new int[26];
        int maxK[]=new int[26];
        for(int i=0;i<26;i++){
            lastPos[i]=-1;
            maxK[i]=0;
        }
        int len=s.length();
        for(int i=0;i<len;i++){
            char ch=s.charAt(i);
            int pos=(int)(ch-'a');
            int diff=i-lastPos[pos];
            if(diff>maxK[pos])
                maxK[pos]=diff;
            lastPos[pos]=i;
        }
        for(int i=0;i<26;i++){
            if(len-lastPos[i]>maxK[i])
                maxK[i]=len-lastPos[i];
        }
        int k=Integer.MAX_VALUE;
        for(int i=0;i<26;i++){
            if(lastPos[i]>=0)
                k=Math.min(k,maxK[i]);
        }
        System.out.println(k);
	}
	static int nextInt()throws IOException{
		InputStream in=System.in;
        int ans=0;
        byte b=0;
        while ((b>47 && b<58) || ans == 0){
            if(b>=48 && b<58)
                ans=ans*10+(b-48);
            b=(byte)in.read();
        }
        return ans;
    }
}