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;

public class TaskC {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int[] maxK = new int[(int)'z'+1];
		int[] lastIndex = new int[(int)'z'+1];
		for(int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			int k = i - lastIndex[(int)c];
			maxK[(int)c] = Math.max(maxK[(int)c], k);		
			lastIndex[(int)c] = i;		
		}
		int minK = 10000000;
		for(int i = (int)'a'; i < (int)'z' + 1; i++) {
			int k = Math.max(maxK[i], Math.max(s.length() - lastIndex[i], s.indexOf(i)+1));
			minK = Math.min(minK, k);
		}
		System.out.println(minK);
	}
}
