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
//stan hu tao
//join nct ridin by first year culture reps
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.System.out;
import java.util.*;
import java.io.*;
import java.math.*;

public class x888C
{
    public static void main(String hi[]) throws Exception
    {
        BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
        char[] arr = infile.readLine().toCharArray();
        int N = arr.length;
        int low = 1;
        int high = N;
        while(low != high)
        {
            int mid = (low+high)/2;
            boolean valid = false;
            for(int c=0; c < 26; c++)
            {
                if(valid)
                    break;
                int curr = 0;
                for(int i=0; i < mid; i++)
                    if(arr[i]-'a' == c)
                        curr++;
                int min = curr;
                for(int i=mid; i < N; i++)
                {
                    if(arr[i]-'a' == c)
                        curr++;
                    if(arr[i-mid]-'a' == c)
                        curr--;
                    min = min(min, curr);
                }
                if(min > 0)
                    valid = true;
            }
            if(valid)
                high = mid;
            else
                low = mid+1;
        }
        System.out.println(low);
    }
    public static int[] readArr(int N, BufferedReader infile, StringTokenizer st) throws Exception
    {
        int[] arr = new int[N];
        st = new StringTokenizer(infile.readLine());
        for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        return arr;
    }
}