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
//package codeforces.div2;

import java.util.*;

public class KDominantCharacter {

   static public void print(String s) {


        HashMap<Character, List<Integer>> map = new HashMap<>();

        for(int i = 0; i < s.length(); i++) {
            if(map.containsKey(s.charAt(i))) {

                List<Integer> l = map.get(s.charAt(i));
                l.add(i);
                map.put(s.charAt(i), l);
            } else {
                List<Integer> l = new ArrayList<>();
                l.add(-1);
                l.add(i);
                map.put(s.charAt(i), l);
            }
        }

        int min = Integer.MAX_VALUE;
        for(Map.Entry<Character, List<Integer>> entry : map.entrySet()) {

            List<Integer> l = entry.getValue();
            int max = 0;
            for(int j = 1; j < l.size(); j++) {
                int diff = l.get(j) - l.get(j-1);
                max = Math.max(diff, max);
            }
            max = Math.max(max, s.length() - l.get(l.size() - 1));
            min = Math.min(min, max);
        }
        System.out.print(min);
    }

    public static void main(String []args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        print(s);
    }
}
