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 P888C {
	static char[] alphabet = new char[26];
	
	public static boolean isDomSpec(String s, char x, int k){
		int counter = 0;
		boolean contains = false;
		for(int i = 0; i < s.length(); i++){
			if(s.charAt(i) == x){
				counter = 0;
				contains = true;
			}
				
			else{
				counter++;
			}
			if(counter == k)
				return false;
		}
		return (true && contains);
	}
	
	public static boolean isDom(String s, int k){
		for(int i = 0; i < 26; i++){
			if(isDomSpec(s, alphabet[i], k)){
				return true;
			}
		}
		return false;
	}
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();
		for(int i = 0; i < 26; i++){
			alphabet[i] = (char)(i + 97);
		}
		
		int start = 1;
        int end = s.length();
        int mid = -1;
        int value =s.length();
        while (start <= end) {
            mid = (start + end) / 2;
            if (isDom(s, mid)){ 
                end = mid - 1;
                value = mid;
            }
            else 
                start = mid + 1;
        }
		System.out.println(value);
	}
}
