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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import javafx.util.Pair;

public class Main
{
   

    public static void main(String args[])
    {
        FastScanner input = new FastScanner();
      String s = input.next();
      int ans  = Integer.MAX_VALUE;
        for (int i = 'a'; i <='z'; i++) {
            int max = Integer.MIN_VALUE;
            int c = 0;
            for (int j = 0; j < s.length(); j++) {
                if(s.charAt(j)==i)
                {
                    c=0;
                }
                else
                    c++;
                max = Math.max(max, c);
            }
                 ans = Math.min(ans, max);
        }
        System.out.println(ans+1);
   
    }

    static class FastScanner
    {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next()
        {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {

            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine() throws IOException
        {
            return br.readLine();
        }
    }

}
