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 KDominantCharacter {
  public static class Data {
    public int prev;
    public int curr;
    public int maxGap;
    
    public Data(int curr) {
      prev = -1;
      this.curr = curr;
      maxGap = Integer.MIN_VALUE;
      maxGap();
    }
    
    public void newCurr(int curr) {
      prev = this.curr;
      this.curr = curr;
      maxGap();
    }
    
    private void maxGap() {
      maxGap = Math.max(maxGap, curr - prev);
    }
  }
  
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    char[] s = in.next().toCharArray();
    int n = s.length;
    
    Map<Character, Data> map = new HashMap<Character, Data>();
    for (int i = 0; i < n; i++) {
      char currChar = s[i];
      if (!map.containsKey(currChar)) {
        map.put(currChar, new Data(i));
      } else {
        map.get(currChar).newCurr(i);
      }
    }
    
    int minWindow = Integer.MAX_VALUE;
    for (Map.Entry<Character, Data> entry : map.entrySet()) {
      Data currData = entry.getValue();
      currData.newCurr(n);
      minWindow = Math.min(minWindow, currData.maxGap);
    }
    
    System.out.println(minWindow);
  }
}