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.Scanner;
import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.Math.*;

public class Main {

    static class FastScanner {
        StringTokenizer tok = new StringTokenizer("");
        BufferedReader in;

        FastScanner() {
            in = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() throws IOException {
            while (!tok.hasMoreElements())
                tok = new StringTokenizer(in.readLine());
            return tok.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }

    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        Scanner in = new Scanner(System.in);

        String s;
        s = input.next();
        int ans = (int)1e9;
        int n = s.length();
        for( char ch = 'a' ; ch <= 'z' ; ch++ ){
            int gap = 0 ;
            int last = -1;
            for( int i = 0 ; i < n ; i++ ){
                if( s.charAt(i) == ch ){
                    gap = Math.max(gap,i-last);
                    last = i ;
                }
            }
            gap = Math.max(gap,n-last);
            ans = Math.min(ans,gap);
        }
        System.out.println(ans);
    }
}

