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.util.*;
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;

public class tr0 {
	static PrintWriter out;
	static StringBuilder sb;
	static int mod = 1000000007;
	static long inf = (long) 1e16;
	static int[][] ad;
	static int n, g;
	static long[][][] memo;
	static HashSet<Integer> h;
	static long[] a;
	static HashSet<Integer> leaves;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		out = new PrintWriter(System.out);
		int ans = Integer.MAX_VALUE;
		String s = sc.nextLine();
		int n = s.length();
		for (int i = 0; i < 26; i++) {
			int l = -1;
			int tem = 0;
			int u = -1;
			int tem6 = 0;
			for (int j = 0; j < n; j++) {
				if (s.charAt(j) != (char) (i + 'a'))
					continue;
				if (l == -1) {
					tem = j + 1;
					tem6 = n - j;
					l = j;
				} else {
					u = 0;
					tem = Math.max(j - l, tem);
					l = j;
				}
			}
			tem6 = n - l;
			// if(u==-1)
			tem = Math.max(tem, tem6);
			if (l != -1)
				ans = Math.min(ans, tem);
		}
		System.out.println(ans);
		out.close();
	}

	static int[] ans;

	static void dfs(int u, int p) {
		if (p != -1)
			ans[u] = Math.min(u, ans[p]);
		for (int v : ad[u])
			if (p != v) {
				dfs(v, u);
			}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

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

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

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public int[] nextArrInt(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public long[] nextArrLong(int n) throws IOException {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}