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.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.prefs.BackingStoreException;

public class prog {
	static String s;

	static int bin_s() {
		int l = 0, r = s.length() + 1;
		while (l != r) {
			int m = (l + r) / 2;
			boolean ok = chek(m);
			if (ok)
				r = m;
			else
				l = m + 1;
		}
		return l;
	}

	static boolean chek(int k) {
		if (k == 0)
			return false;
		int l = 0, r = k - 1;
		int cur[] = new int['z' + 10];
		int mas[] = new int['z' + 10];
		for (int i = 0; i < r; i++)
			cur[s.charAt(i)]++;
		for (; r < s.length(); r++, l++) {
			cur[s.charAt(r)]++;
			for (int j = 0; j < mas.length; j++) {
				if (cur[j] != 0)
					mas[j]++;
			}
			cur[s.charAt(l)]--;
		}
		for (int i = 0; i < mas.length; i++) {
			if (mas[i] == s.length() - k + 1)
				return true;
		}
		return false;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		s = in.next();
		out.println(bin_s());
		in.close();
		out.close();

	}

}
