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;
import java.util.*;
public class MyClass {
    public static void main(String args[]) {
        Scanner sc =new Scanner (System.in);
        char[] a = sc.next().toCharArray();
        int[] last = new int[26];
        int[] max = new int[26];
        
        Arrays.fill(last, -1);
        int n = a.length;
        int res = n;
        for (int i = 0; i < a.length; i++) {
            int c = a[i] - 'a';
            max[c] = Math.max(max[c], i - last[c]);
            last[c] = i;
        }
        for (int i = 0; i < 26; i++)
            max[i] = Math.max(max[i], n - last[i]);
        for (int c = 0; c < 26; c++)
            res = Math.min(res, max[c]);
        System.out.println(res);
    }
}
