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.*;
import java.util.*;

public class A implements Runnable{
	public static void main (String[] args) {new Thread(null, new A(), "_cf", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);

		String str = fs.nextLine();
		int n = str.length();
		int res = (int)1e9;
		int lo = 1, hi = str.length();
		for(int bs = 0; bs < 50 && lo <= hi; bs++) {
			int k = (lo + hi) >> 1;
			int[] freq = new int[26];
			boolean[] works = new boolean[26];
			for(int i = 0; i < k; i++) {
				works[str.charAt(i)-'a'] = true;
				freq[str.charAt(i)-'a']++;
			}
			for(int i = k; i < n; i++) {
				freq[str.charAt(i-k)-'a']--;
				freq[str.charAt(i)-'a']++;
				if(freq[str.charAt(i-k)-'a'] == 0) works[str.charAt(i-k)-'a'] = false;
			}
			boolean good = false;
			for(int i = 0; i < 26; i++) {
				if(works[i]) {
					good = true;
				}
			}
			if(!good) {
				lo = k + 1;
			} else {
				hi = k - 1;
				res = Math.min(res, k);
			}
		}
		out.println(res);
		
		out.close();
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		public FastScanner() {
			try	{
				br = new BufferedReader(new InputStreamReader(System.in));
				//                br = new BufferedReader(new FileReader("testdata.out"));
				st = new StringTokenizer("");
			} catch (Exception e){e.printStackTrace();}
		}
		public String next() {
			if (st.hasMoreTokens())	return st.nextToken();
			try {st = new StringTokenizer(br.readLine());}
			catch (Exception e) {e.printStackTrace();}
			return st.nextToken();
		}
		public int nextInt() {return Integer.parseInt(next());}
		public long nextLong() {return Long.parseLong(next());}
		public double nextDouble() {return Double.parseDouble(next());}

		public String nextLine() {
			String line = "";
			try {line = br.readLine();}
			catch (Exception e) {e.printStackTrace();}
			return line;
		}
		public Integer[] nextIntegerArray(int n) {
			Integer[] a = new Integer[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		} 
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public char[] nextCharArray() {return nextLine().toCharArray();}
	}

}