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
/** https://codeforces.com/problemset/problem/888/C
 *  idea: two pointer
 */

import java.util.Scanner;

public class KDominantCharacter {
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       String str = sc.next();
       int len = 'z' - 'a' + 1;
       int[] arrC = new int[len];
       int[] arrCLastIdx = new int[len];
       char[] orgArr = str.toCharArray();
       int idx;
       for (int i=0; i < orgArr.length; i++) {
           idx = orgArr[i] - 'a';
           if (i - arrCLastIdx[idx]>= arrC[idx]) {
               arrC[idx] = (arrC[idx] == 0) ? (i - arrCLastIdx[idx] + 1) : (i - arrCLastIdx[idx]);
           }
           arrCLastIdx[idx] = i;
       }
       
       int k = orgArr.length;
       for (int i=0; i < arrC.length; i++) {
           if (orgArr.length - arrCLastIdx[i] > arrC[i]) {
                arrC[i] = orgArr.length - arrCLastIdx[i];
           }
           if (arrC[i] < k) {
               k = arrC[i];
           }
           //for(int i=0; i < arrC.length; i++) {
           //System.out.println(String.format("%c, %d, %d", i+ 'a', arrC[i], arrCLastIdx[i]));
       //}
       }

       System.out.println(k);
   } 
}