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.HashMap;
import java.util.Scanner;

public class C888 {

	public static void main(String[] args) {
		
		Scanner s = new Scanner(System.in);
		String word = s.next();
		HashMap<Character, Integer> maxMap = new HashMap<>();
		HashMap<Character, Integer> lastMap = new HashMap<>();
		for (int i = 0; i < word.length(); i++) {
			
			char c = word.charAt(i);
			if (maxMap.containsKey(c)) {
				int dif = i - lastMap.get(c);
				if (maxMap.get(c) < dif) {
					maxMap.put(c, dif);
				}
			} else {
				maxMap.put(c, i + 1);
			}
			lastMap.put(c, i);
			
		}
		for (Character c : maxMap.keySet()) {
			
			int dif = word.length() - lastMap.get(c);
			if (maxMap.get(c) < dif) {
				maxMap.put(c, dif);
			}
			
		}
		int min = word.length();
		for (Character c : maxMap.keySet()) {
			min = Math.min(min, maxMap.get(c));
		}
		System.out.println(min);
		
	}
	
}
