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.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
import javax.swing.ScrollPaneConstants;

import org.omg.Messaging.SyncScopeHelper;

public class Solution {
static	Scanner input = new Scanner(System.in);





	public static void main(String[] args) {

		String s = input.nextLine();
		
		ArrayList<Integer> [] a = new ArrayList[26];
		
		for (int i = 0 ; i < 26 ; i++) {
			a[i] = new ArrayList<>();
			a[i].add(-1);
		}

		
		for (int i = 0 ; i < s.length() ; i++) {
			
			int indx =(int) s.charAt(i)-97;
		
			a[indx].add(i);
		}
		for (int i = 0 ; i < 26 ; i++) {
			a[i].add(s.length());
		}
		
		int min = 1000000000+1;
		
		for (int i = 0 ; i < 26  ; i++) {
			if (a[i].size()>2) {
				
			int maxDiff = 0 ;
			

			for (int j = 0 ; j < a[i].size()-1 ; j++) {
				
				int diff = Math.abs(a[i].get(j+1)-a[i].get(j));
				
				if (diff>maxDiff) 
					maxDiff = diff;
				
			}
			if (min>maxDiff) 
				min = maxDiff;
		}
		}
		System.out.println(min);


		
	}
}