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 C888 {
	
	int n;
	char[] chs;

	
	private void solve() throws Exception {
		chs = nextToken().toCharArray();
		n = chs.length;
		int left = 0;
		int right = n;
		while(left < right - 1) {
			int mid = (left+right)/2;
			if(verify(mid)) right = mid;
			else left = mid;
		}
		out.println(right);
	}
	
	boolean verify(int k) {
		boolean[] removed = new boolean[26];
		int[] count = new int[26];
		for(int i = 0; i < k; i++) count[chs[i]-'a']++;
		for(int i = 0; i < 26; i++) if(count[i] == 0) removed[i] = true;
		for(int i = k; i < n; i++) {
			int add = chs[i]-'a';
			int remove = chs[i-k]-'a'; 
			count[remove]--;
			count[add]++;
			if(count[remove] == 0) removed[remove] = true;
		}
		boolean ok = false;
		for(int i = 0; i < 26; i++) ok = ok||!removed[i];
		return ok;
	}

	public static void main(String[] args) {
		new C888().run();
	}

	private BufferedReader in;
	private PrintWriter out;
	private StringTokenizer tokenizer;

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			tokenizer = null;
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	private int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	private long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	private float nextFloat() throws IOException {
		return Float.parseFloat(nextToken());
	}

	private String nextLine() throws IOException {
		return new String(in.readLine());
	}

	private String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(in.readLine());
		}
		return tokenizer.nextToken();
	}


}

