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.*;
import java.io.*;
public class CF888C {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      String s = sc.next();
      int n = s.length();
      int k = n + 5;
      int d,p;
      for(char i = 'a'; i <= 'z'; i++){
         d = 0;
         p = -1;
         for(int j = 0; j < n; j++){
            if(s.charAt(j) == i){
               d = Math.max(j - p, d);
               p = j;
            }
         }
         d = Math.max(n - p, d);
         k = Math.min(k, d);
      }
      System.out.println(k);
   }
}