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.Scanner;
import java.util.Arrays;
public class KDominantCharacter {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] in = sc.nextLine().toCharArray();
		int[] maxDistance = new int[26];
		int[] lastIndex = new int[26];
		Arrays.fill(lastIndex, -1);
		for(int i = 0; i < in.length; i++){
			maxDistance[in[i] - 'a'] = Math.max(maxDistance[in[i]-'a'], i-lastIndex[in[i]-'a']);
			lastIndex[in[i] - 'a'] = i;
		}
		int min = in.length;
		for(int i = 0; i < 26; i++){
			min = Math.min(min, Math.max(maxDistance[i], in.length - lastIndex[i]));
		}
		System.out.println(min);
	}
}