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.*;

public class KDominantChar {

    static String text;
    static char[] alphabet;

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        text = br.readLine();
        int len = text.length();
        alphabet = new char[]{'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s',
                              't','u','v','w','x','y','z'};
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < 26; i++)
        {
            char n = alphabet[i];
            int k1 = 1, k2 = -1;
            for (int j = 0; j < len; j++)
            {
                char s = text.substring(j,j+1).charAt(0);
                if (n == s)
                    k1 = 1;
                else
                    k1++;
                k2 = Math.max(k1,k2);
            }
            ans = Math.min(ans,k2);
            //System.out.println(n + ": k1 = " + k1 + " k2 = " + k2 + " ans = " + ans);
        }
        System.out.println(ans);
    }
}
