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.List;
import java.util.Scanner;

public class problemC {

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);

        String s = scan.nextLine();
        boolean[] visited = new boolean[s.length()];

        int letterMax = 0;
        int totMin = Integer.MAX_VALUE;
        for (int i = 0; i < s.length(); i++) {
            if (visited[i]) {
                continue;
            }
            letterMax = i + 1;
            visited[i] = true;
            int k = i;
            int j = i;
            for (j = i + 1; j < s.length(); j++) {
                if (s.charAt(j) == s.charAt(k)) {
                    visited[j] = true;
                    if (letterMax < j - k) {
                        letterMax = j - k;
                    }
                    k = j;
                }
            }
            if (letterMax < j - k) {
                letterMax = j - k;
            }
            if (letterMax < totMin) {
                totMin = letterMax;
            }
        }

        System.out.print((totMin));

    }
}
