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

public class CodeForces_Contest0002 {
	
	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);
		String strK = scan.nextLine();
		int latinL[] = new int['z'-'a'+1];
		for (int i='a'; i<'z'+1; i++)
		{
			int distMin = 0, lastD = -1, j=0;
			for (j=0; j<strK.length(); j++)
			{
				if (strK.charAt(j) == (char) i)
				{
					if (j-lastD > distMin) distMin = j-lastD;
					lastD = j;
				}
			}
			latinL[(char) i-'a']=Math.max(distMin,j-lastD);
		}
		System.out.println(Arrays.stream(latinL).min().getAsInt());
		scan.close();
	}
}
