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

public class C {
	
	public static void main(String[] args) {
		try (final Scanner sc = new Scanner(System.in)) {
			
			final int ALPHA = 26;
			int[] prev = new int[ALPHA];
			int[] min_len = new int[ALPHA];
			for(int i = 0; i < ALPHA; i++){ 
				prev[i] = -1;
				min_len[i] = Integer.MIN_VALUE;
			}
			
			char[] ins = sc.next().toCharArray();
			for(int i = 0; i < ins.length; i++){
				final int in = ins[i] - 'a';
				final int p = prev[in];
				
				if(p < 0){ 
					prev[in] = i;
					if(i == 0){
						min_len[in] = 0;
					}else{
						min_len[in] = (i + 1);
					}
				}else{
					//System.out.println((char)(in + 'a') + " " + p + " : " + prev[in] + " " + i);
					
					prev[in] = i;
					min_len[in] = Math.max(min_len[in], (i - p));
					//System.out.println(min_len[in]);
				}
			}
			
			for(int i = 0; i < ALPHA; i++){
				if(prev[i] < 0){ continue; }
				
				min_len[i] = Math.max(min_len[i], ins.length - prev[i]);
			}
			
			int min = Integer.MAX_VALUE;
			for(int i = 0; i < ALPHA; i++){
				if(prev[i] < 0){ continue; }
				
				//System.out.println((char)('a' + i) + " : " + min_len[i]);
				min = Math.min(min, min_len[i]);
			}
			/*
			for(int i = 0; i < ALPHA; i++){
				System.out.println((char)('a' + i) + " : " + min_len[i]);
			}//*/
			System.out.println(min);
		}
	}
		
	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

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

		private void getLine() {
			try {
				while (!hasNext()) {
					tok = new StringTokenizer(br.readLine());
				}
			} catch (IOException e) { /* ignore */
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() {
			getLine();
			return tok.nextToken();
		}

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

		public void close() {
			try {
				br.close();
			} catch (IOException e) { /* ignore */
			}
		}
	}
}
