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

public class KDominantCharacter {
	private static final FastReader in = new FastReader();
	private static final PrintWriter out = new PrintWriter(System.out);

	public static void main(String[] args) {
		Solver sol = new Solver();
		int tt = 1;
		sol.solve(tt);
		out.close();
	}

	private static final class Solver {
		public void solve(int testCase) {
			char[] a = in.next().toCharArray();
			int n = a.length;
			int ans = Integer.MAX_VALUE;
			for (int alpha = 0; alpha < 26; ++alpha) {
				int take = -1, max = 0;
				for (int i= 0; i < n; ++i) {
					if (a[i] - 'a' == alpha) {
						max = Math.max(max, i - take);
						take = i;
					}
				}
				max = Math.max(max, n - take);
				ans = Math.min(ans, max);
			}
			out.println(ans);
		}
	}

	private static final class FastReader {
		private BufferedReader br;
		private StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);
			st = null;
		}

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