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

public class Main {
	//////
	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

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

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}

	//////
	public static long modularExponentiation(long x, long n, long M) {
		long result = 1;
		while (n > 0) {
			if (n % 2 == 1)
				result = (result * x) % M;
			x = (x * x) % M;
			n = n / 2;
		}
		return result;
	}

	public static long modularExponentiation1(long x, long n) {
		long result = 1;
		while (n > 0) {
			if (n % 2 == 1)
				result = (result * x);
			x = (x * x);
			n = n / 2;
		}
		return result;
	}

	/////
	static long d(int x, int y) {
		if (Math.abs(x - y) > 1) {
			return y - x;
		} else
			return 0;

	}

	static int closestSquare(int num) {

		if (num == 0) {
			return -1;
		}
		int root = (int) Math.sqrt(num);
		int another = root + 1;
		root = root * root;
		another = another * another;
		if (another - num > num - root) {
			return num - root;
		} else
			return another - num;

	}

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

		FastReader scan = new FastReader();
		PrintWriter pw = new PrintWriter(System.out);

		String input = scan.next();
		char[] A = input.toCharArray();
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < 26; i++) {
			int l = 0, r = 0;
			int max1 = 0;
			while (r < A.length) {
				while (r < A.length && A[r] != (char) (i + 'a')) {
					r++;
				}
				max1 = Math.max(max1, r - l + 1);
				l=r+1;
				r=r+1;
			}
			min=Math.min(min,max1);
		}
		System.out.println(min);
	}
}
