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 C 
{

	static StringBuilder st = new StringBuilder();
	
	public static void main(String[] args) throws Exception 
	{

		Scanner sc = new Scanner(System.in);
		
		PrintWriter out = new PrintWriter(System.out);
		
		char [] c = sc.next().toCharArray();
		
		int n = c.length ; 
		
		int start = 1  , end = n , k = n;
		
		while(start <= end)
		{
			int mid = (start + end) / 2 ; 
			
			int freq [] = new int [26];
			boolean [] vis = new boolean [26] ;
			boolean [] noZeros = new boolean [26] ;
			
			for(int i = 0 ; i < mid ; i++)
			{
				freq[c[i] - 'a']++;
				vis[c[i] - 'a'] = true;
				noZeros [c[i] - 'a'] = true ; 
			}
			
			boolean atLeast = false ; 
			
			for(int i = mid ; i < n ; i++)
			{
				freq[c[i - mid ] - 'a']--;
				freq[c[i] - 'a']++;
				noZeros[c[i - mid ] - 'a'] &= freq[c[i - mid ] - 'a'] > 0 ; 
			
			}
			
			for(int x = 0 ; x < 26 ; x++)
				if(vis[x])
					atLeast |= noZeros[x] ;
			
			if(atLeast)
			{
				k = mid ; 
				end = mid - 1 ; 
			}
			else
				start = mid + 1 ; 
		}
		
		out.println(k);
		
		
		
		
		out.flush();
		out.close();

	}
	
	static class Scanner 
	{
		BufferedReader br;
		StringTokenizer st;

		Scanner(InputStream in) 
		{
			br = new BufferedReader(new InputStreamReader(System.in));
		}

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

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

		long nextLong() throws Exception {
			return Long.parseLong(next());
		}

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

	}

	static void shuffle(int[] a) {
		int n = a.length;
		for (int i = 0; i < n; i++) {
			int r = i + (int) (Math.random() * (n - i));
			int tmp = a[i];
			a[i] = a[r];
			a[r] = tmp;
		}
	}

}