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

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] c = in.next().toCharArray();

        int[] max = new int[26];
        int[] last = new int[26];
        Arrays.fill(last, -1);
        for (int i=0; i<c.length; i++) {
            int ch = c[i]-'a';
            int dist = Math.abs(last[ch]-i);
            max[ch] = Math.max(max[ch], dist);
            last[ch] = i;
        }
        for (int i=0; i<26; i++) {
            int ch = i;
            int dist = Math.abs(last[ch]-c.length);
            max[ch] = Math.max(max[ch], dist);
        }

        int ans = Integer.MAX_VALUE;
        for (int i=0; i<26; i++) {
            ans = Math.min(ans, max[i]);
//            System.out.println((char)(i+'a') +" " + max[i]);
        }
        System.out.println(ans);
    }
}