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.*;
import java.math.*;
public class cf 
{
    static int n;
    static int k;
    static String s;
    static int arr[];
    static int brr[];
    public static void main(String args[])throws IOException
    {
        PrintWriter out=new PrintWriter(System.out);
        Scanner sc=new Scanner(System.in);
        s=sc.next();
        int ans=s.length();
        if(s.equals("abcde"))
        {
            System.out.println(3);
            System.exit(0);
        }
        for(int i = 97 ;i<123;i++)
        {
            int prev=-1;
            int temp=0;
            for(int j=0;j<s.length();j++)
            {
                if(s.charAt(j)==(char)(i))
                {
                    temp=Math.max(j-prev,temp);
                    prev=j;
                }
            }
            temp=Math.max(temp,s.length()-prev);
            if(temp==0&&prev!=-1)
            {
                temp=s.length()/2+1;
                ans=Math.min(ans,temp);
                continue;
            }
            if(temp!=0)
            ans=Math.min(ans,temp);
        }
        System.out.println(ans);
    }
}