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 CF888C {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[] cc = br.readLine().toCharArray();
		int n = cc.length;
		int[] pp = new int[26];
		Arrays.fill(pp, -1);
		int[] gg = new int[26];
		for (int i = 0; i < n; i++) {
			int c = cc[i] - 'a';
			int g = i - pp[c];
			if (gg[c] < g)
				gg[c] = g;
			pp[c] = i;
		}
		int k = n;
		for (int c = 0; c < 26; c++)
			if (pp[c] != -1) {
				gg[c] = Math.max(gg[c], n - pp[c]);
				if (k > gg[c])
					k = gg[c];
			}
		System.out.println(k);
	}
}
