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.*;
import java.io.*;
import java.lang.*;
public class C32E {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc =new Scanner(System.in);
		String s =sc.next();
		ArrayList<Integer> a[] =(ArrayList<Integer> [])new ArrayList[26];
		int l=s.length();
		for(int i=0;i<26;i++){
			a[i]=new ArrayList<Integer>();
		}
		for(int i=0;i<l;i++){
			a[s.charAt(i)-'a'].add(i);
		}
		int max[] =new int[26];
		for(int i=0;i<26;i++){
			Iterator<Integer> it=a[i].iterator();
			int pre=-1;
			while(it.hasNext()){
				int curr=it.next();
				int diff=curr-pre;
				if(diff>max[i]){
					max[i]=diff;
				}
				pre=curr;
			}
			if(l-pre>max[i]){
				max[i]=l-pre;
			}
		}
		int min=l/2+1;
		for(int i=0;i<26;i++){
			if(max[i]!=0 && max[i]<min){
				min=max[i];
			}
		}
		System.out.println(min);
	}
}
