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.Scanner;
public class Main {
    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        String str = s.next();
        int gap[] = new int[26];
        int index[] = new int[26];
        for(int i = 0; i < 26; i++){
            index[i] = -1;
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < str.length(); i++){
            gap[str.charAt(i) - 'a'] = Math.max(gap[str.charAt(i) - 'a'],i - index[str.charAt(i) - 'a']);
            index[str.charAt(i) - 'a'] = i;
        }
        for(int i = 0; i < 26; i++){
            gap[i] = Math.max(gap[i],str.length() - index[i]);
        }
        for(int i = 0; i < 26; i++){
            min = Math.min(min,gap[i]);
        }
        System.out.println(min);
    }
}