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 k_dominant_character
{
	public static void main(String args[]) throws Exception
	{
		BufferedReader f=new BufferedReader(new InputStreamReader(System.in));
		// BufferedReader f=new BufferedReader(new FileReader("k_dominant_character.in"));
		String in=f.readLine();
		// for(int x=1;x<=in.length()/2+1;x++)
		int ans=1<<20;
		int low=0;
		int high=in.length();
		while(high>=low)
		{
			int pos=(low+high)/2;
			int[] freq=new int[26];
			for(int a=0;a<pos;a++)
				freq[in.charAt(a)-97]++;
			boolean[] has=new boolean[26];
			int count=0;
			for(int a=0;a<26;a++)
				if(freq[a]!=0)
				{
					has[a]=true;
					count++;
				}
			for(int a=pos;a<in.length();a++)
			{
				freq[in.charAt(a-pos)-97]--;
				freq[in.charAt(a)-97]++;
				if(freq[in.charAt(a-pos)-97]==0&&has[in.charAt(a-pos)-97])
				{
					count--;
					has[in.charAt(a-pos)-97]=false;
				}
				if(count==0) break;
			}
			if(count!=0)
			{
				ans=pos;
				high=pos-1;
			}
			else
				low=pos+1;
		}
		System.out.println(ans);
	}
}