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 Codeforces {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        //int n = s.nextInt();
        String in = s.next();

        int l = in.length();

        int sigma = 26;
        int[] maxDist = new int[sigma];
        int[] lastPos = new int[sigma];
        for (int i = 0; i < sigma; i++) {
            lastPos[i] = -1;
            maxDist[i] = -1;
        }

        for (int i = 0; i < l; i++) {
            int index = in.charAt(i)-'a';
            maxDist[index] = Math.max(maxDist[index], i - lastPos[index]);
            lastPos[index] = i;
        }

        int result = l;
        for (int i = 0 ; i < sigma; i++) {
            maxDist[i] = Math.max(l-lastPos[i], maxDist[i]);
            result = Math.min(result, maxDist[i]);
        }
        System.out.print(result);
    }
}
