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.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
     
public class contest {
	public static void intersect(int[] in,int[] arr) {
		for(int i=0;i<in.length;i++) {
			in[i] = Math.min(arr[i], in[i]);
		}
	}
	public static boolean check(String s,int mid) {
		int[] arr = new int[26];
		int[] in = new int[26];
		for(int i=0;i<in.length;i++)
			in[i] = 10000000;
		for(int i=0;i<mid;i++) {
			arr[s.charAt(i)-'a']++;
		}
		intersect(in, arr);
		//System.out.println(Arrays.toString(in));
		int j = 0;
		for(int i=mid;i<s.length();i++) {
			arr[s.charAt(j)-'a']--;
			arr[s.charAt(i)-'a']++;
			intersect(in, arr);
			j++;
			//System.out.println(Arrays.toString(in));
		}
		for(int i=0;i<arr.length;i++) {
			if(in[i]>0)return true;
		}
		return false;
	}
	public static void main(String[] args) throws IOException {
		//Scanner sc = new Scanner(new FileReader(new File("/home/mina/eclipse-workspace/HelloWorld/src/test")));
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		String s = sc.next();
		int a = 1;
		int b = s.length();
		int ans = s.length();
		int mid = 0;
		while(a<b) {
			mid = (a+b)/2;
			
			if(check(s, mid)) {
				ans = mid;
				b = mid-1;
			}else {
				a = mid+1;
			}
		}
		for(int i=Math.max(1, mid-2);i<Math.min(s.length(), mid+2);i++) {
			if(check(s, i)) {
				ans = i;
				break;
			}
		}
		pw.println(ans);
		pw.flush();
		pw.close();
	}
}
class P{
	int l;
	int r;
	int step;
	public P(int a,int b,int c) {
		l = a;
		r = b;
		step = c;
	}
	public String toString() {
		return "("+l + " " + r + " " + step+")";
	}
}
    
    class Scanner {
        StringTokenizer st;
        BufferedReader br;
     
        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }
     
        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }
     
        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
     
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
     
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
     
        public String nextLine() throws IOException {
            return br.readLine();
        }
     
        public double nextDouble() throws IOException {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
    double res = 0, f = 1;
    boolean dec = false, neg = false;
    int start = 0;
    if (x.charAt(0) == '-') {
        neg = true;
        start++;
    }
    for (int i = start; i < x.length(); i++)
        if (x.charAt(i) == '.') {
            res = Long.parseLong(sb.toString());
            sb = new StringBuilder("0");
                dec = true;
            } else {
                sb.append(x.charAt(i));
                if (dec)
                    f *= 10;
            }
        res += Long.parseLong(sb.toString()) / f;
        return res * (neg ? -1 : 1);
    }
 
    public boolean ready() throws IOException {
        return br.ready();
        
    }
}