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 ER32C {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int min = Integer.MAX_VALUE;
		int[] dist = new int[26];
		int[] lastidx = new int[26];
		Arrays.fill(lastidx, -1);
		String s = scan.nextLine();
		for(int i = 0; i < s.length(); i++){
			char c = s.charAt(i);
			if(lastidx[c-'a'] == -1){
				dist[c-'a'] = i+1;
			}
			else{
				dist[c-'a'] = Math.max(dist[c-'a'], i-lastidx[c-'a']);
			}
			lastidx[c-'a'] = i;
		}
		//System.out.println(Arrays.toString(dist));
		for(int i = 0; i < 26; i++){
			if(lastidx[i] != -1){ 
				dist[i] = Math.max(dist[i], s.length()-lastidx[i]);
				min = Math.min(min, dist[i]);
			}
		}
		//System.out.println(Arrays.toString(dist));
		System.out.println(min);
	}
}
