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 Solution {
	private static Scanner input = new Scanner(System.in);
	
	public static void main(String[] args) {
		String s = input.nextLine();
		
		int res = 1000000;
		for (char c = 'a'; c <= 'z'; c++) {
			int currDist = 1, maxDist = -1;
			for (int i = 0; i < s.length(); i++) {
				/*if (c == 'c')
					System.out.println(i + " " + currDist);*/
				
				if (i == s.length() - 1 && s.charAt(i) != c)
					currDist++;
				
				if (s.charAt(i) == c || i == s.length() - 1) {
					maxDist = Math.max(maxDist, currDist);
					currDist = 1;
				}
				else {
					currDist++;
				}
			}
			
			if (maxDist != -1) {
				res = Math.min(res, maxDist);
				//System.out.println(c + " " + maxDist);
			}
		}
		
		System.out.println(res);
	}	
}