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
    // Where there is a will, there is a way !
import java.io.*;
import java.util.*;
import java.math.*;

public class Solution {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st;
        /*
inputCopy
abacaba
outputCopy
2
inputCopy
zzzzz
outputCopy
1
inputCopy
abcde
outputCopy
3  */
        char[] arr = br.readLine().toCharArray();
        int l = 1, r = arr.length;
        int ans = arr.length;
        while (l <= r) {
            int mid = (l + r) / 2;
            //System.out.println("mid="+mid);
            if (check(arr, mid)) {
                ans = mid;
                //System.out.println("check true for mid="+mid);
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        pw.println(ans);
        pw.flush();
        pw.close();
    }

    public static boolean check(char[] arr, int mid) {
        int[] count = new int[26];
        boolean[] valid = new boolean[26];
        for (int i = 0; i < mid; ++i) {
            ++count[arr[i] - 97];
        }
        
        for (int i = 0; i < 26; ++i) {
            if (count[i] > 0) {
                valid[i] = true;
            }
        }
        for (int i = mid; i < arr.length; ++i) {
            ++count[arr[i] - 97];
            --count[arr[i - mid] - 97];
            if (count[arr[i - mid] - 97] == 0) {
                valid[arr[i - mid] - 97] = false;
                //System.out.println(arr[i-mid]+" turned false");
            }
        }
        for(int i=arr.length-mid+1;i<arr.length;++i)
        {
            
        }
        for (int i = 0; i < 26; ++i) {
            if (valid[i]) {
                //System.out.println("Found : "+(char)(i+97));
                return true;
            }
        }
        return false;
    }
}
