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.*;

public class CF_888C{
  public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int length = s.length();
        char[] arr = new char[length];
        for (int i = 0; i < length; i++) {
            arr[i] = s.charAt(i);
        }
        
        int[] before = new int[26];
        Arrays.fill(before, -1);
        
        int[] max = new int[26];
        
        for (int i = 0; i < length; i++) {
            int a = arr[i] - 97;
            max[a] = Math.max(max[a], i - before[a]);
            before[a] = i; 
        }
        
        int k = Integer.MAX_VALUE;
        
        for (int i = 0; i < 26; i++) {           
            max[i] = Math.max(max[i], length - before[i]);
            k = Math.min(k, max[i]);
        }
        
        System.out.println(k);
  }
}