Snuke can change a string t of length N into a string t' of length N - 1 under the following rule:

* For each i (1 ≤ i ≤ N - 1), the i-th character of t' must be either the i-th or (i + 1)-th character of t.



There is a string s consisting of lowercase English letters. Snuke's objective is to apply the above operation to s repeatedly so that all the characters in s are the same. Find the minimum necessary number of operations.

Constraints

* 1 ≤ |s| ≤ 100
* s consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:


s


Output

Print the minimum necessary number of operations to achieve the objective.

Examples

Input

serval


Output

3


Input

jackal


Output

2


Input

zzz


Output

0


Input

whbrjpjyhsrywlqjxdbrbaomnw


Output

8
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        long j = 0 ;
        List<Character> ls = new LinkedList<>();
        for(char c: s.toCharArray())
            ls.add(c);

        System.out.println(ls.stream().distinct().map(e -> solve.apply(e,s)).min(Comparator.naturalOrder()).get());


    }



    static BiFunction<String,Character,String> step = (before,c) -> {
        String s1,s2;
        StringBuilder sb = new StringBuilder();
        if(before !=  null && before.length() > 0) {
            s1 = before.substring(0, before.length() - 1);
            s2 = before.substring(1,before.length());
            for(int i = 0;i < before.length() -1;i++)
            {
                if(c.equals(s1.charAt(i)) || c.equals(s2.charAt(i)))
                {
                    sb.append(c);
                }
                else
                    sb.append(s1.charAt(i));
            }
            return sb.toString();
        }
        else
            return "";
    };

    static Predicate<String> check = s -> {
        List<Character> ls = new LinkedList<>();
        for(char c: s.toCharArray())
            ls.add(c);
        if(ls.stream().distinct().count() == 1)
            return true;
        else
            return false;
    };
    static BiFunction<Character,String,Integer> solve = (c,s) -> {
        for (int i = 0; ; i++) {
            if (check.test(s))
                return i;
            else
                s = step.apply(s,c);
        }
    };
}
