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 kDominant{
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String s = br.readLine();
    Set<Character> settid = new HashSet<Character>();
    int min = s.length();
    for(int i = 0; i < s.length(); i++){
      if(!settid.contains(s.charAt(i))){
        int lengd = -1;
        int tempL = 0;
        for(int g = 0; g < s.length(); g++){
          if(s.charAt(g) == s.charAt(i)){
            if(tempL > lengd){
              lengd = tempL;
            }
            tempL = 0;
          }
          else tempL++;
          if(g == s.length()-1) if(tempL > lengd)lengd = tempL;
        }
        if(lengd < min && lengd != -1) min = lengd;
        settid.add(s.charAt(i));
      }
    }
    System.out.println(min+1);
  }
}