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 Question {
	
	String input = "";
	InputStream in;
	PrintWriter out;
	
	void solve() {
		
		char[] arr = in_s().toCharArray();
		int len = arr.length;
		int min = Integer.MAX_VALUE;
		for(char ch = 'a' ; ch <= 'z'  ; ++ch) {
			int pos = -1;
			int distance = 0;
			for(int i = 0 ; i < len ; ++i){
				if(arr[i] == ch) {
					distance = Math.max(distance , i - pos);
					pos = i;
				}
			}
			distance = Math.max(distance , len - pos);
			min = Math.min(distance , min);
		}
		out.println(min);
	}
	
	public static void main(String[] args) throws Exception {
		new Question().run();
	}
	
	void run() throws Exception
	{
		out = new PrintWriter(System.out);
		in = input.isEmpty() ? System.in : new ByteArrayInputStream(input.getBytes());
		long start = System.currentTimeMillis();
		solve();
		out.flush();
		if(!input.isEmpty())
			printlast(System.currentTimeMillis()-start+"ms");
	}
	
	private byte[] buffer = new byte[1024];
	public int ptr=0,len=0;
	
	private int readByte()  // input 
	{
		if(len == -1)throw new InputMismatchException();
		if(ptr >= len){
			ptr = 0;
			try { 
				len = in.read(buffer); 
			} catch (IOException e) { throw new InputMismatchException(); }
			if(len <= 0)
				return -1;
		}
		return buffer[ptr++];
	}
	
	private boolean isSpace(int c) {   // check for white space 
		return !(c > 32 && c < 127); 
	}
	
	private int check() { 
		int n; 
		while((n = readByte()) != -1 && isSpace(n)); 
		return n;
	}
	
	private double in_d() { 	// input for double
		return Double.parseDouble(in_s());
	}
	
	private char in_c() {     // input for char
		return (char)check();
	}
	
	private String in_s()  // input for one word
	{
		int n=check();
		StringBuilder st = new StringBuilder();
		while(!(isSpace(n)))  { 
			st.appendCodePoint(n);
			n=readByte();
		}
		return st.toString();
	}
	
	private String in_sl()  // input for one line
	{
		int n=check();
		StringBuilder st = new StringBuilder();
		while(!(isSpace(n) && n!=' ')) {
			st.appendCodePoint(n);
			n=readByte();
		}
		return st.toString();
	}
	
	
	private char[] in_s(int n)  // input for char array
	{
		char[] arr = new char[n];
		int a=check();
		int count=0;
		while(count < n && !(isSpace(a))){
			arr[count++]=(char)a;
			a=readByte();
		}
		return n == count ? arr : Arrays.copyOf(arr,count);
	}
	private char[][] in_ac(int n, int m)  // input for char 2D array
	{
		char[][] arr = new char[n][];
		for(int i=0 ; i<n ; i++)
			arr[i] = in_s(m);
		return arr;
	}
	private int[] in_ai(int n)  // input for int array
	{
		int[] arr = new int[n];
		for(int i = 0;i < n;i++)
			arr[i] = in_i();
		return arr;
	}
	private int in_i() // input for int
	{
		int num = 0, a;
		boolean minus = false;
		while((a = readByte()) != -1 && !((a >= '0' && a <= '9') || a == '-'));
		if(a == '-'){
			minus = true;
			a = readByte();
		}
		
		while(true){
			if(a >= '0' && a <= '9'){
				num = num*10 + (a-'0');
			}else{
				return minus ? -num : num;
			}
			a = readByte();
		}
	}
	
	private long in_l() // input for long
	{
		long num = 0;
		int a;
		boolean minus = false;
		while((a = readByte()) != -1 && !(( a >= '0' && a <= '9') || a == '-'));
		if(a == '-'){
			minus = true;
			a = readByte();
		}
		
		while(true){
			if(a >= '0' && a <= '9'){
				num = num * 10 + (a - '0');
			}else{
				return minus ? -num : num;
			}
			a = readByte();
		}
	}
	
	private void printlast(Object... o) { 
		if(input.length() > 0)
			System.out.println(Arrays.deepToString(o)); 
	}
} 
