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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

	//UPSOLVE

public class DominantCharacter {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
	      String s = st.nextToken();
	      
	      int n = s.length();
	      int minKVal = n + 5;
	      int dominant;
	      int weak;
	      
	      for(char i = 'a'; i <= 'z'; i++){
	         dominant = 0;
	         weak = -1;
	         for(int j = 0; j < n; j++){
	            if(s.charAt(j) == i){
	            	dominant = Math.max(j - weak, dominant);
	            	weak = j;
	            }
	         }
	         dominant = Math.max(n - weak, dominant);
	         minKVal = Math.min(minKVal, dominant);
	      }
	      
	      System.out.println(minKVal);
	}
}
