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
/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
     Scanner sc=new Scanner(System.in);
     String s=sc.next();
     int n=s.length();
     
     int[] index=new int[26];
     int[] maxLen=new int[26];
     
     Arrays.fill(index,-1);
     
     for(int i=0;i<n;i++){
      int x=(int)s.charAt(i)-97;
      maxLen[x]=Math.max(maxLen[x],i-index[x]);
      index[x]=i;
     }
     for(int i=0;i<n;i++){
      int x=(int)s.charAt(i)-97;
      maxLen[x]=Math.max(maxLen[x],n-index[x]);
     }
     int min=Integer.MAX_VALUE;
     for(int i=0;i<26;i++)if(maxLen[i]>0)min=Math.min(min,maxLen[i]);
     
     System.out.println(min);
	}
}