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.util.*;

public class Main {
    static int get(char c) {
        return Character.getNumericValue(c) - Character.getNumericValue('a');
    }

    static void solve() throws IOException {
        int character[] = new int[26]; // store last position of character a..z, initialized to -1
        Arrays.fill(character, -1);
        int maxDistance[] = new int[26];
        String s = input.readLine();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            int val = get(c);
            maxDistance[val] = Math.max(maxDistance[val], i - character[val] - 1);
            character[val] = i;
        }
        for (int i  = 0; i < 26; i++) {
            maxDistance[i] = Math.max(maxDistance[i], n - character[i] - 1);
        }
        int min = (int) 1e8;
        for (int i = 0; i < 26; i++) {
            min = Math.min(min, maxDistance[i] + 1);
        }
        ans.append(min).append('\n');
        output.write(ans.toString());
        output.flush();
        output.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().solve();
    }

    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder ans = new StringBuilder();
    static String line;
    static StringTokenizer stringTokenizer;

    static int ni1() throws IOException {
        return Integer.parseInt(input.readLine());
    }

    static int ni2() throws IOException {
        return Integer.parseInt(stringTokenizer.nextToken());
    }

    static long nl1() throws IOException {
        return Long.parseLong(input.readLine());
    }

    static long nl2() {
        return Long.parseLong(stringTokenizer.nextToken());
    }

    static void rl() throws IOException {
        stringTokenizer = new StringTokenizer(input.readLine());
    }
}
