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

public class KDominant {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner input = new Scanner(System.in);
		String s = input.next();
		HashSet<Character> set = new HashSet<Character>();
		for(int i=0; i<s.length();i++){
			set.add(s.charAt(i));
		}
		int min = Integer.MAX_VALUE;
		for(char c : set){
			min = Math.min(min,min1(s,c));
		}
		System.out.println(min);
	}

	
	private static int min1(String s, char c){
		int a = s.indexOf(c);
		int min = a+1;
	     int last = a;	
		while(s.indexOf(c,a+1)!=-1){
			a = s.indexOf(c,a+1);
			//last = a;
			min  = Math.max(a-last,min);
			last = a;
		}
		min  = Math.max(min,s.length()-a);
		return min;
	}
}
