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.io.*;
import java.util.*;
import java.util.regex.*;
public class vk18
{
    public static void main(String[]stp) throws Exception
    {
    	Scanner scan=new Scanner(System.in);
    	PrintWriter pw = new PrintWriter(System.out);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        char []c=st.nextToken().toCharArray();
        int j=0,pre=0,max=0,min=Integer.MAX_VALUE;
        for(char i='a';i<='z';i++)
        {
        	pre=0;
        	max=Integer.MIN_VALUE;
        	for(j=0;j<c.length;j++)
        	{
        		if(c[j]==i) { max=Math.max(max,(j+1-pre)); pre=j+1; }
        	}
        	max=Math.max(c.length+1-pre,max);
        	min=Math.min(min,max);
        }
        pw.print(min);
    	pw.flush();

    }

    
}