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


public class Main {
    
    
    
    public static void main(String[] args) throws IOException {
       FastScanner sc=new FastScanner(System.in);
       char a[]=sc.next().toCharArray();
       int n=a.length;
       int prv[]=new int[26];
       int max[]=new int[26];
       Arrays.fill(max, -1);
       for(int i=0;i<n;i++){
           int c=a[i]-'a';
           if(prv[c]==0){
               prv[c]=i+1;
               max[c]=i+1;
           }else{
               max[c]=Math.max(i+1-prv[c], max[c]);
               prv[c]=i+1;
           }
       }
       int ans=Integer.MAX_VALUE;
       for(int i=0;i<26;i++){
           max[i]=Math.max(n+1-prv[i], max[i]);
           ans=Math.min(ans, max[i]);
       }
        System.out.println(ans);
        
    }
     //__________________________________________________________
    static class FastScanner {
	    BufferedReader br;
	    StringTokenizer st;
            public FastScanner(InputStream i) throws FileNotFoundException {
	        br =  new BufferedReader(new InputStreamReader(i));
	        st = new StringTokenizer("");
	    }
	    public String next() throws IOException {
	        if(st.hasMoreTokens())return st.nextToken();
                else st = new StringTokenizer(br.readLine());
	        return next();
	    }
	    public int nextInt() throws IOException {return Integer.parseInt(next());}
	    public long nextLong() throws IOException {return Long.parseLong(next());}
	    public double nextDouble() throws IOException {return Double.parseDouble(next());}
	}
}
  
