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.*;
import java.io.*;
import java.math.*;

public class Main {

    static Scanner input = new Scanner(new BufferedReader(new InputStreamReader(System.in)));

    public static void main(String[] args) {
        String s = input.next();
        int minKdom = s.length();
        for (char c = 'a'; c <= 'z'; c++) {
            int Kdom = dom(c, s);
            if (minKdom > Kdom) {
                minKdom = Kdom;
            }
        }
        System.out.println(minKdom);
    }

    static int dom(char c, String s) {
        int last;
        for (last = 0; last < s.length(); last++) {
            if (s.charAt(last) == c) {
                break;
            }
        }
        int maxLen = last + 1;
        for (int i = last + 1; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                if (maxLen < i - last) {
                    maxLen = i - last;
                }
                last = i;
            }
        }
        if (maxLen < s.length() - last) {
            maxLen = s.length() - last;
        }
        return maxLen;
    }
}