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.util.ArrayList;
public class Main{   
     static class Pair{
     int x;
     int y;
       Pair(){
       
       }
       Pair(int x,int y){
       this.x=x;
       this.y=y;
       }
     }
    
 
    public static void main(String[] args)
    {
    Scanner param = new Scanner(System.in);
    
    String a=param.next();
    HashMap<Character,Integer>h=new HashMap<>();
    HashMap<Character,Integer>h1=new HashMap<>();
    
    for(int i=0;i<a.length();i++){
    if(h.containsKey(a.charAt(i))){
    int diff=h.get(a.charAt(i));
    int max=Math.max(h1.get(a.charAt(i)),i-diff);
    h1.put(a.charAt(i),max);
    h.put(a.charAt(i),i);
     //System.out.println(h1);
    
    }
    else{
    h.put(a.charAt(i),i);
    h1.put(a.charAt(i),i+1);
    // System.out.println(h1);
    }
    }
   // System.out.println(h1);
    for(int i=0;i<a.length();i++){
        int diff=h.get(a.charAt(i));
        int m=a.length();
        int max=Math.max(h1.get(a.charAt(i)),m-diff);
       h1.put(a.charAt(i),max);
         //System.out.println(h1);
    }
    int max=Integer.MAX_VALUE;
  // System.out.println(h1);
  /// System.out.println(h);
    
    
    for(int i=0;i<a.length();i++){
   
    max=Math.min(h1.get(a.charAt(i)),max);
    
    }
    System.out.println(max);
   
   
    
    } 
    
}

