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.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
        String str = s.next();
        HashMap<Character,ArrayList<Integer>> m = new HashMap<>();
        for(int i=0;i<str.length();i++){
            char key = str.charAt(i);
            if(m.get(key)==null) m.put(key, new ArrayList<Integer>());
            m.get(key).add(i);
        }
        int min = str.length();
        
        for(Map.Entry<Character, ArrayList<Integer>> ee : m.entrySet()){
            Character key = ee.getKey();
            ArrayList<Integer> list = ee.getValue();
            int max = list.get(0) + 1;
            for(int i=1;i<list.size();i++){
                int temp = list.get(i)-list.get(i-1);
                if(max<temp) max = temp;
            }
            max = Math.max(max, str.length()-list.get(list.size()-1));
            //System.out.println(max);
            if(min>max) min = max;
        }
        System.out.println(min);
    }
}
