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 A{
	public static void main(String args[]){
		Scanner scan = new Scanner(System.in);
		String s = scan.next();
		int length=s.length();
		int[] arr = new int[26];
		for(int i=0;i<s.length();i++){
		    arr[s.charAt(i)-'a']=1;
		    
		}
		for(char a='a';a<='z';a=(char)(a+1)){
			int prev=-1,len=0;
			if(arr[a-'a']==0) continue;
			for(int i=0;i<s.length();i++){
				if(s.charAt(i)==a){
					if(i-prev>len){
						len=i-prev;
					}
					prev=i;
				}
			}
		
			if(s.length()-prev>len){
				len=s.length()-prev;
			}
			
			if(len<length){
				length=len;
			}
	
		}
		
		
		System.out.println(length);
	}
}