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 CubesForMasha{
	public static void main(String[] args) {
		//int n;
		Scanner sc = new Scanner(System.in);
		//n = sc.nextInt();
		//sc.nextLine();
		String s = new String(sc.nextLine());
		
		int[][] distance = new int[26][2];
		
		for(int i = 0; i < 26; i++) {
			distance[i][0] = -1;
		}
		for(int i = 0; i < s.length() ; i++){
			int temp = (int)(s.charAt(i)-'a');
			
			int dis = i - distance[temp][0] ;
			//if(distance[temp][0] == 0)dis++;
			 distance[temp][1] = Math.max(distance[temp][1], dis);
			 distance[temp][0] = i;
		}
		for(int i = 0; i < s.length(); i++) {
			int temp = (int)(s.charAt(i)-'a');
			int dis = s.length() - distance[temp][0] ;
			
			
			 distance[temp][1] = Math.max(distance[temp][1], dis);
		}
		int min = 100000000;
		
		
		for(int i = 0; i < s.length(); i++) {
			int temp = s.charAt(i) - 'a';
		//	System.out.printf("%d %d\n",distance[temp][0] , distance[temp][1]);
			
			min = Math.min(min, distance[temp][1]);
		}
		
		System.out.print(min);
		
	}
}