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.*;
public class q1 
{
public static void main(String[] args)
{
	Scanner sc=new Scanner(System.in);
	String s=sc.next();
	int n=s.length();
	char[] ch=s.toCharArray();
	//long n=sc.nextInt();
	ArrayList<Integer>[] v=new ArrayList[26];
	for(int i=0;i<26;i++)v[i]=new ArrayList();
	for(int i=0;i<26;i++)
	{
		v[i].add(-1);
	}
	for(int i=0;i<n;i++)
	{
		int ind=(int)ch[i]-(int)'a';
		v[ind].add(i);
	}
	for(int i=0;i<26;i++)
		v[i].add(n);
	int min=Integer.MAX_VALUE;
	for(int i=0;i<26;i++)
	{
		
		if(v[i].size()==2)
			continue;
		int max=Integer.MIN_VALUE;
		for(int j=1;j<v[i].size();j++)
		{
			int diff=v[i].get(j)-v[i].get(j-1);
			if(diff>max)
				max=diff;
		}
		if(max<min)
			min=max;
	}
	System.out.print(min);
}  

}