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.*;

public class solution
{


	public static void main(String args[]) throws IOException
	{
		// 
		Scanner sc=new Scanner(System.in);
		// BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));

		// int n=sc.nextInt();
	
		String str=sc.next();
		char ar[]=str.toCharArray();
		int n=str.length();
		int arr[]=new int[n];
		for(int i=0;i<n;i++)
		{
			arr[i]=ar[i]-'a';
		}


		int counter[]=new int[26];
		//udlr

		
		for(int j=0;j<26;j++)
		{
			int count=0;

			for(int i=0;i<n;i++)
			{
				if(arr[i]==j)
				{
					if(count>counter[j])
					{
						counter[j]=count;
					}
					count=0;	
				}
				else if(i==n-1)
				{
					count++;
					if(count>counter[j])
					{
						counter[j]=count;
					}
				}
				else
					count++;
			}
	
		}
		int mini=Integer.MAX_VALUE;

		for(int i=0;i<26;i++)
		{
			if(counter[i]<mini)
			{
				mini=counter[i];
			}
		}

		System.out.println(mini+1);

			


		
		

	
	}
}

	