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 A
{
      public static void main(String ar[]) throws Exception
      {
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            char c[]=br.readLine().toCharArray();
            int n=c.length;
            int a[][]=new int[n+1][26];
            for(int i=0;i<n;i++)
            {
                  for(int j=0;j<26;j++)
                  {
                        char d=(char)(j+97);
                        if(d==c[i])
                         a[i+1][j]=a[i][j]+1;
                        else
                         a[i+1][j]=a[i][j];
                  }
            }
            int l=1,r=n;
            while(r-l>1)
            {
              int k=(l+r)/2;
            
            int b[]=new int[26];
            for(int i=k;i<=n;i++)
            {
                  for(int j=0;j<26;j++)
                   if(a[i][j]-a[i-k][j]>0)
                    b[j]++;
            }
            
            int t=0;
            for(int i=0;i<26;i++)
             if(b[i]==n-k+1)
              t++;
            
            if(t>0)
             r=k;
            else
             l=k;
            }
            
            if(r-l==1)
            {
                 int k=l;
            
            int b[]=new int[26];
            for(int i=k;i<=n;i++)
            {
                  for(int j=0;j<26;j++)
                   if(a[i][j]-a[i-k][j]>0)
                    b[j]++;
            }
            
            int t=0;
            for(int i=0;i<26;i++)
             if(b[i]==n-k+1)
              t++;
            
           // System.out.println(Arrays.toString(b));
            if(t>0)
             r=l;
            }
            System.out.println(r);
      }
}