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 try67{
	public static void main(String s[]){
		Scanner sc = new Scanner(System.in);
		String st = sc.next();
		int arr[] = new int[27];
		int min = Integer.MAX_VALUE;
		HashMap<Character,Integer> hm = new HashMap<>();
		for(int i=0;i<st.length();i++){
			hm.put(st.charAt(i),1);
		}
		ArrayList<Character> keys = new ArrayList<>(hm.keySet());
		for(char i=0;i<keys.size();i++){
			char ch = keys.get(i);
			int ans=Integer.MIN_VALUE;
			ArrayList<Integer> al = new ArrayList<>();
			for(int j=0;j<st.length();j++){
				if(st.charAt(j)==ch){
					al.add(j);
				}
			}
			for(int j=0;j<al.size();j++){
					boolean b=false;
					if(j==0){
						int diff = al.get(j)+1;
						ans = Math.max(diff,ans);
						b=true;
					}
					if(j==al.size()-1){
						int diff = st.length()-al.get(j);
						ans = Math.max(diff,ans);
						b=true;
						
					}
				
					if(j!=0){
					int diff = al.get(j)-al.get(j-1);
					ans = Math.max(diff,ans);}
				
			}
			min = Math.min(ans,min);
		}
		System.out.println(min);
		
		
	}
	
}