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.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class CF {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[] ch = br.readLine().toCharArray();
		boolean[] checked = new boolean[26];
		Arrays.fill(checked, false);

		int min = Integer.MAX_VALUE;
		for (int i = 0; i < ch.length; ++i) {
			int max = -1;
			if (!checked[ch[i] - 'a']) {
				checked[ch[i] - 97] = true;
				int lastOcc = -1;
				for (int occ = 0; occ < ch.length; ++occ) {
					if (ch[occ] == ch[i]) {
						max = Math.max(occ - lastOcc - 1, max);
						lastOcc = occ;
					}
				}
				max = Math.max(ch.length - lastOcc - 1, max);
				min = Math.min(max + 1, min);
			}
		}
		System.out.println(min);
	}

}