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 com.codeforces.contest888;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class KDominantCharacter {
    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);

        String input = in.next();

        int[] k = new int[26];
        int[] idx = new int[26];

        Arrays.fill(k, 0);
        Arrays.fill(idx, -1);


        int len = input.length();
        for (int i = 0; i < len; i++) {
            char c = input.charAt(i);
            k[c - 'a'] = Math.max(k[c - 'a'], i - idx[c - 'a']);
            idx[c - 'a'] = i;
        }

        int result = Integer.MAX_VALUE;

        for (int i = 0; i < 26; i++) {
            if (k[i] == 0)
                k[i] = len;
            else
                k[i] = Math.max(k[i], len-idx[i]);
            result = Math.min(result, k[i]);
        }

        System.out.println(result);

    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

    }
}
