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 info.stochastic;

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class C {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {

        boolean ok(String s, int len) {
            int[] letters = new int[26];
            int counter = 0;
            for (int i = 0; i < len; i++) {
                letters[s.charAt(i) - 'a']++;
                counter++;
            }

            for (int i = len; i < s.length(); i++) {
                if (letters[s.charAt(i) - 'a'] != 0) {
                    letters[s.charAt(i) - 'a']++;
                    counter++;
                }

                if (letters[s.charAt(i - len) - 'a'] > 0) {
                    letters[s.charAt(i - len) - 'a']--;
                    counter--;
                }
            }
            return counter > 0;
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            String s = in.next();

            int left = 1;
            int right = s.length();
            int ans = 1;
            while (left <= right) {
                int mid = (left + right) >>> 1;

                if (ok(s, mid)) {
                    ans = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }

            }

            out.print(ans);
        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

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

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

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}
