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 MinValue {
    static int check(String s, int K) 
        { 
            for (int ch = 0; ch < 26; ch++) { 
                char c = (char)( 'a' + ch); 
          
                int last = -1; 
          
                boolean found = true; 
                for (int i = 0; i < K; i++) 
                    if (s.charAt(i) == c) 
                        last = i; 
          
                if (last == -1) 
                    continue; 
          
                for (int i = K; i < s.length(); i++) { 
                    if (s.charAt(i) == c) 
                        last = i; 
          
                    if (last <= (i - K)) { 
                        found = false; 
                        break; 
                    } 
                } 
                if (found) 
                    return 1; 
            } 
            return 0; 
        } 
    
    
    public static int minValue(String s){ 
    
        int l=1, h = s.length(),ans = 0;;
        while(l<=h){
          int mid  = l + (h-l)/2;
          if(check(s,mid)==1){
            ans = mid;
            h = mid -1;
            
          }else {
            l = mid+1;
          }
      }
      return ans;
    }
    
    public static void main(String args[]) throws IOException {
      
      //write your code here
      Scanner sc = new Scanner(System.in);
        String s = sc.next();
        System.out.println(minValue(s));
      
      sc.close();
    }
  }