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 MyClass {
    public static void main(String args[]) {
        Scanner sc=new Scanner(System.in);
        String s=sc.next();
        int m=(s.length()/2)+1;
        for(char ch='a';ch<='z';ch++)
        {
            int ind=-1;
            int max=0;
            for(int i=0;i<s.length();i++)
            {
                if(s.charAt(i)==ch)
                 {
                     max=Math.max(max,i-ind);
                      ind=i;
                 }
            }
            max=Math.max(max,s.length()-ind);
            if(max!=0)
            m=Math.min(m,max);
        }
       System.out.println(m);
    }
}
     