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.HashMap;
import java.util.Optional;
import java.util.Scanner;

public class Main3 {

    public static void main(String[] args) {
       // tests();
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        HashMap<Character,Integer> map1 = new HashMap<>();
        HashMap<Character,Integer> map2 = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if(!map1.containsKey(c)){
                map1.put(c,i);
                map2.put(c,i+1);
            }else {
                int before = map1.get(c).intValue();

                int value = i - before;
                if(value == 1) value++;
                if(!map2.containsKey(c)){
                    map2.put(c, value);
                }else {
                    int beforeValue = map2.get(c).intValue();
                    map2.put(c,Math.max(beforeValue, value));
                }
                map1.put(c,i);
            }
        }
        for (Character character:
             map1.keySet()) {
            int value = map2.get(character).intValue();
            map2.put(character,Math.max(value,s.length() - map1.get(character).intValue()));
        }
        Optional<Integer> min = map2.values().stream().min((o1, o2) -> o1 < o2 ? -1 : 1);
        if(map1.keySet().size() == 1) {
            System.out.println("1");
            return;
        }

        if(min.isPresent()){
            System.out.println(min.get());
        }else {
                int x = (s.length() + 1) / 2;
                if((s.length() ) % 2 == 0){
                    x+=1;
                }
                System.out.println(x);

        }

    }




}
