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.math.BigInteger;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collections;
	import java.util.HashMap;
	import java.util.Iterator;
	import java.util.List;
	import java.util.Scanner;
	
	public class SequenceWithDigits {
	
		static Scanner sc= new Scanner(System.in);
		static List<Integer> C;
		static List<Integer> B;
		
		
		
		public static void main(String[] args) {
			
				
			String s=sc.next();
			
			HashMap<Character,ArrayList<Integer>> map=new HashMap<>();
			ArrayList<Integer> temp;
			
			for(int i=0;i<s.length();i++) {
				temp=new ArrayList<>();
				char key=s.charAt(i);
				if(map.containsKey(key)) {
					temp=map.get(key);
					temp.add(i);
					map.put(key,temp);
				}
				else {
					temp.add(i);
					map.put(key, temp);
				}
				
				
			}
			int min=(s.length())/2+1;
		//System.out.println(map);
			int m=Integer.MIN_VALUE;

			for(HashMap.Entry<Character,ArrayList<Integer>>entry:map.entrySet()) {
				
temp=entry.getValue();
//if(temp.size()<=2)continue;
m=Integer.MIN_VALUE;
m=Math.max(temp.get(0)+1,s.length()-temp.get(temp.size()-1));
if(temp.size()==1)continue;
				inner:for(int i=0;i<temp.size()-1;i++) m=Math.max(m, temp.get(i+1)-temp.get(i));
//if(temp.size()==2)m=temp.get(1)-temp.get(0);
			
				min=Math.min(min,m);
				
			}
			System.out.println(min);
		
			}}
