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 KDomChar {
public static void main(String[] args) {
	Scanner s = new Scanner(System.in);
	char[] line = s.nextLine().toCharArray();
	s.close();
	HashMap<Character,Integer> longestDist = new HashMap<Character,Integer>();
	HashMap<Character,Integer> lastSeen = new HashMap<Character,Integer>();
	int index = 1;
	for (char c:line) {
		int distSinceLast = index - lastSeen.getOrDefault(c, 0);
		lastSeen.put(c, index);
		if(distSinceLast>longestDist.getOrDefault(c, -1)) {
			longestDist.put(c, distSinceLast);
		}
		index++;
	}
	for (Character c:longestDist.keySet()) {
		int distSinceLast = index - lastSeen.get(c);
		if(distSinceLast>longestDist.get(c)) {
			longestDist.put(c, distSinceLast);
		}
	}
	int minLongestDist = Integer.MAX_VALUE;
	for(int i: longestDist.values()) {
		if(i<minLongestDist) {
			minLongestDist = i;
		}	
	}
	System.out.println(minLongestDist);
}
}
