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

public class K_dominant {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scn = new Scanner(System.in);
		String str = scn.nextLine();
		int count = 0;
		int max = 0;
		HashMap<Character, Integer> hmap = new HashMap<>();
		ArrayList<Character> arr=new ArrayList<>();
		for (int i = 0; i < str.length(); i++) {
			if (!hmap.containsKey(str.charAt(i)))
			{
				hmap.put(str.charAt(i), 1);
				arr.add(str.charAt(i));
			}
			else {

				hmap.put(str.charAt(i), hmap.get(str.charAt(i)) + 1);
			}
		}
		count = 0;
		//System.out.println(arr);
		int min=Integer.MAX_VALUE;
		for(int j=0;j<arr.size();j++)
		{	count=0;max=0;
			for(int i=0;i<str.length();i++)
			{
				if(str.charAt(i)==arr.get(j))
				{
					count=0;
					//System.out.println(count);
				}
				else
				{
					count++;
				}
				if(max<count)
				{
					max=count;
				}
				//System.out.println(count+" "+arr.get(j)+" "+str.charAt(i));
			}
			//System.out.println(max+" "+arr.get(j));
			if(min>max)
			{
				min=max;
			}
		}
		System.out.println(min+1);
	}

}
